2021年中国大学生程序设计竞赛女生专场C. 连锁商店

题目链接：传送门

官方思路：
如果某家公司开的连锁店数量不超过 1，那么可以无视 “每家公司的红包只能领一份” 这个限制，这是因为任何一条路线都无法访问多次该公司开的商店。如果某家公司开的连锁店数量至少为 2，那么这样的公司数最多为 n/2 ≤18。
由于第二类公司数量并不多，因此可以使用状态压缩动态规划来求解这个问题。设f[i][S]表示从 1 出发到达了 i 点，一路上访问过的第二类公司集合为 S 时，访问过的第一类公司的红包总价值最大是多少，枚举下一个景点进行转移。时间复杂度 O(nn2^(n/2) )。

具体分析：
先将每家公司重新分类，
连锁店不超过1家(<=1)的作为第一类，并将其赋为编号-1(表示是第一类)；
连锁店超过一家(>=2)的作为第二类，并对所有的第二类公司(共kind个)重新编号从0到kind-1。

    for(int i=1;i<=n;i++){
   
        scanf("%d",&c[i]);
        vis[c[i]]++;
    }
    for(int i=1;i<=n;i++){
     ///公司的分类
        if(vis[i]>=2) num[i] = kind++;
        else num[i] = -1;
    }
1
2
3
4
5
6
7
8
9
10

而后开始写状态转移dp[pre][S]到dp[now][S]的转移
若pre到now之间有一条缆车，则可以从pre的状态转移到now的状态，此时需要讨论该景点的商店所属公司是否为第一类，即num[c[now]]是否为-1。
具体讨论见代码：

void dfs(int now,int pre)
{
   
    if(num[c[now]]==-1) {
    ///第一类直接加上
        for(int i=0;i<(1<<kind);i++){
   
            dp[now][i] = max(dp[now][i],dp[pre][i] + w[c[now]]); ///直接继承以前的状态
            dp[now][(1<<kind)] = max(dp[now][(1<<kind)],dp[now][i]); ///dp[now][(1<<kind)]储存1到now的可以获得的最大值
        }
    }
    else {
    ///第二类选择转移
        for(int i=0;i<(1<<kind);i++){
   
            int t1 = (1<<num[c[now]]);  ///表示要选择该位置，1<<num[c[now]]为该位置在S中对应的二进制位置
            if(t1&i){
     ///若t1&i!=0则表示当pre的状态为i时该公司的优惠券已经被选择
                dp[now
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18