脚本宝典收集整理的这篇文章主要介绍了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）全部内容，希望文章能够帮你解决2021年中国大学生程序设计竞赛女生专场 C. 连锁商店 （状压dp）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。