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

本文主要是介绍2021年中国大学生程序设计竞赛女生专场 C. 连锁商店 （状压dp），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 题意：每个点都属于某个公司，公司对应一个权值，对于一条路径，如果一些点属于同一家公司，那么贡献只能算一次，给你一张图，路径只能从小的往大的走，现在问你从\(1\)到每个点的路径上的最大权值是多少。

• 题解：\(n\)最大为\(36\)，出现多个点的公司数最大为\(\frac{n}{2}\)，不难发现，对于一条路径，如果这条路径上的一些点仅有一家公司属于他们，这种情况是固定的，出现状态分裂的情况为出现多个点的那些公司，而这题的\(n\)很小，我们可以用二进制来压缩出现多个点的公司的状态。

  设\(dp[i][j]\)表示，当前在\(i\)点，出现多个点的公司的选择情况为\(j\)，\(to\)表示上一个点，那么有：

  1.\(i\)只有一家公司拥有他，那么我们直接从上一个点转移即可，\(dp[i][j]=max(dp[to][j]+w[c[i]])\).

  2.\(i\)属于出现多个点的公司，那么先找到他在出现多个点的公司的新编号，那么根据当前的\(j\)直接转移就好

  具体看代码吧，这里注意，有的人可能会说，假如我找到\(i\)的时候，\(j\)的状态表示了后面一些还没跑到的点会不会有问题，这里是没问题的，因为只有跑过的点会对状态有影响，没有遍历到的点选还是不选都一个样,因为值都是一样的

• 代码：

  #include <bits/stdc++.h>
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  #define rep(a,b,c) for(int a=b;a<=c;++a)
  #define per(a,b,c) for(int a=b;a>=c;--a)
  const int N = 2e6 + 10;
  const int mod = 998244353;
  const int INF = 0x3f3f3f3f;
  using namespace std;
  typedef pair<int,int> PII;
  typedef pair<ll,ll> PLL;
  ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
  ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
  
  int n,m;
  int c[N],w[N];
  int dp[40][N];
  vector<int> edge[N];
  unordered_map<int,int> mp;
  vector<int> v;
  int main() {
  	scanf("%d %d",&n,&m);
  	for(int i=1;i<=n;++i){
  		scanf("%d",&c[i]);
  		mp[c[i]]++;
  	}
  	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
  	for(auto w:mp){
  		if(w.se>1) v.pb(w.fi);
  	}
  	for(int i=1;i<=m;++i){
  		int u,v;
  		scanf("%d %d",&u,&v);
  		edge[v].pb(u);
  	}
  	edge[1].pb(0);
  	for(int i=1;i<=n;++i){
  		int id=-1;
  		for(int j=0;j<(int)v.size();++j){
  			if(c[i]==v[j]){
  				id=j;
  				break;
  			}
  		}
  		if(id==-1){
  			for(int j=0;j<(1<<(int)v.size());++j){
  				for(auto to:edge[i]){
  					dp[i][j]=max(dp[i][j],dp[to][j]+w[c[i]]);
  				}
  			}
  		}
  		else{
  			for(int j=0;j<(1<<(int)v.size());++j){
  				if(j&(1<<id)){
  					for(auto to:edge[i]){
  						dp[i][j]=max(dp[i][j],dp[to][j^(1<<id)]+w[c[i]]);
  					}
  				}
  				else{
  					for(auto to:edge[i]){
  						dp[i][j]=max(dp[i][j],dp[to][j]);
  					}
  				}
  			}
  		}
  		int ans=0;
  		for(int j=0;j<(1<<(int)v.size());++j) ans=max(ans,dp[i][j]);
  
  

这篇关于2021年中国大学生程序设计竞赛女生专场 C. 连锁商店 （状压dp）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！