【状压DP】2021ccpc女生赛 C 连锁商店

深藏阁楼爱情的钟 2024-03-17 09:25 57阅读 0赞

[Problem - C - Codeforces][]

题意：

![114e591cb2614aeaaa4c482dd11f9021.png][]

思路：

一开始想的是对点进行状压，尽管(1<<36)会超时超空间但还是写了

设dp\[s\]\[u\]为走过的**景点**的集合，u为最后一个经过的点的1~i的最大价值

转移就是选一个没走过点转移，如果说原来走过的点中存在和新来的点的公司是同一个的，那么就是+0，否则就是加上点权

#include <bits/stdc++.h>
    
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    //#define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int mxn=50;
    const int mxe=50;
    const int mod=1e9+7;
    
    int N,M,u,v,tot=0;
    int c[mxn],w[mxn],G[mxn][mxn];
    int ans[mxn];
    
    int F(int s,int x){
        for(int i=0;i<N;i++){
            if(((s>>i)&1) && w[c[i]]==x) return 0;
        }
        return x;
    }
    void solve(){
        cin>>N>>M;
        vector<vector<int> > dp=vector<vector<int> > ((1<<25),vector<int> (40));
        for(int i=0;i<N;i++) cin>>c[i],c[i]--;
        for(int i=0;i<N;i++) cin>>w[i];
        for(int i=0;i<M;i++){
            cin>>u>>v;
            u--,v--;
            G[u][v]=1;
        }
        dp[1][0]=w[c[0]];
        for(int s=0;s<(1<<N);s++){
            for(int u=0;u<N;u++){
                if(((s>>u)&1)==0) continue;
                for(int v=0;v<N;v++){
                    if((s>>v)&1) continue;
                    if(!G[u][v]) continue;
                    dp[s|(1<<v)][v]=max(dp[s|(1<<v)][v],dp[s][u]+F(s,w[c[v]]));
                }
            }
        }
        for(int s=0;s<(1<<N);s++){
            for(int u=0;u<N;u++){
                if((s>>u)&1) ans[u]=max(ans[u],dp[s][u]);
            }
        }
        for(int i=0;i<N;i++) cout<<ans[i]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

然后就不会了

事实上是这么做的：

![5eaf3223a0e6464faabe6a722fd01422.png][]

**把n个公司分为两类，第一类是只出现一次的，第二类是出现多次的  
dp\[i\]\[s\]表示经过第二类公司的集合，1~i的最大价值  
关于复杂度：因为都是第二类公司，出现次数都>=2次，因此位数<=18，因此可以存下  
当u能够到达v才能更新新的状态，所以要预处理g数组，g\[u\]\[v\]表示u能够到达v**

参考博客：[2021年中国大学生程序设计竞赛女生专场-C. 连锁商店详解 - 知乎 (zhihu.com)][2021_-C. _ - _ _zhihu.com]

Code：

#include <bits/stdc++.h>
    
    using namespace std;
    using ll = long long;
    
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
    
    	int n, m, tot = 0;
    	cin >> n >> m;
    	vector<int> c(n + 1), w(n + 1), cnt(n + 1), c2(n + 1), book(n + 1), rk(n + 1);
    	vector<vector<int> > g(n + 1, vector<int>(n + 1, 0)), dp(n + 1, vector<int>(1 << (n / 2 + 1), 0)), ve(n + 1);
    	for(int i = 1;i <= n;i++) {
    		cin >> c[i];
    		ve[c[i]].push_back(i);
    	}
    	for(int i = 1;i <= n;i++) {
    		if(ve[i].empty()) continue;
    		if(ve[i].size() == 1) book[ve[i][0]] = 1;
    		else {
    			rk[i] = tot;
    			tot++;
    		}
    	}
    	for(int i = 1;i <= n;i++) cin >> w[i];
    	for(int i = 1;i <= m;i++) {
    		int u, v;
    		cin >> u >> v;
    		g[u][v] = 1;
    	}
    	for(int k = 1; k <= n; k++) {
    		for(int i = 1; i <= n; i++) {
    			for(int j = 1; j <= n; j++) {
    				if(i != j) {
    					g[i][j] |= (g[i][k] & g[k][j]);
    				}
    			}
    		}
    	}
    	if(book[1]) dp[1][0] = w[c[1]];
    	else dp[1][1 << rk[c[1]]] = w[c[1]];
    	for(int st = 0; st < 1 << tot; st++) {
    		for(int u = 1; u <= n; u++) {
    			for(int v = 1; v <= n; v++) {
    				if(!g[u][v]) continue;
    				if(book[v]) {
    					dp[v][st] = max(dp[v][st], dp[u][st] + w[c[v]]);
    				}
    				else {
    					if(!(st >> rk[c[v]] & 1)) {
    						dp[v][st | (1 << rk[c[v]])] = max(dp[v][st | (1 << rk[c[v]])], dp[u][st] + w[c[v]]);
    					}
    				}
    			}
    		}
    	}
    	for(int i = 1;i <= n;i++) cout << *max_element(dp[i].begin(), dp[i].end()) << '\n';
    
    	return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/gym/103389/problem/C
[114e591cb2614aeaaa4c482dd11f9021.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/ec89aed824174ef097c0520cc38094a2.png
[5eaf3223a0e6464faabe6a722fd01422.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/8074a1c2c9e844d5bfa33734443803ad.png
[2021_-C. _ - _ _zhihu.com]: https://zhuanlan.zhihu.com/p/562618319