题意：
给出n个景点，每个景点都属于一个公司，给出每个公司的价值。如果是第一次经过这个公司就会获得对应的价值，问从1出发到每个景点能够获得的最大价值。
n < = 36
思路：
可以看到n的范围不大，也就是说可以用二进制来表示有没有经过某个公司，比如1001就表示已经经过了1 , 4个公司，没有经过2 , 3公司。这样，到达每个节点时，就会有对应的数来表示之前经过公司的状态。
记录每个点的前驱节点，也就是对于给出的u − > v这条边，执行g [ v ] . p u s h _ b a c k ( u )操作，表示v的上一个点可以为u。
考虑从u转移到v的时候会有什么变化，假设u景点属于的公司为c u，v 的为c v。那么就有两种情况，一是没有经过c v，所以现在v的状态就会比u的状态多了c v，同时价值也会增加w [ c v ]；二是经过了c v ，这时候v的状态跟u的状态是相同的，由于以前经过了c v，所以经过v 的时候不会产生贡献。
一个节点的前驱节点有很多个，可以用v e c t o r保存下所有的状态。s t [ i ]里面存放的就是第i个节点的所有状态，那么从u转移到v的时候，就要把所有的状态都枚举一遍。
这样会被完全图卡成O ( n 2 2 n )，会超时。
有两种优化方法，一种是减小前驱节点的数量，一种是减小前驱节点的状态数量。
对于第一种，可以在建图的时候优化。比如对于n = = 4的完全图，实际上有效的边只有1 − > 2 − > 3 − > 4，也就是一条链，因为这样每个点得到的价值才有可能最大。比如边1 − > 2 − > 3比1 − > 3多经过了节点2，前者的价值> = 后者。
对于第二种，从状态上去优化。也是贪心的角度考虑，尽可能的获得最多的价值。如果说10010 ,同时存在的话，肯定是优先选11110去转移，目前的价值最大，以后也才有希望价值较大。
代码：
优化1
// Problem: C. 连锁商店 // Contest: Codeforces - 2021年中国大学生程序设计竞赛女生专场 // URL: https://codeforces.com/gym/103389/problem/C // Memory Limit: 512 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; ll n,m,c[55],w[55]; vector<ll>g[55],p[55]; map<ll,ll>dp[55];//第i个商店状态j的最大值 vector<ll>st[55];///第i个商店有哪些状态 ll ans[maxn];///最大值 ll gg[55][55]; int main(){ n=read,m=read; for(int i=1;i<=n;i++){ c[i]=read; p[c[i]].push_back(i); } rep(i,1,n) w[i]=read; for(int i=1;i<=m;i++){ ll u=read,v=read; //g[v].push_back(u); gg[u][v]=1; } //优化建图 for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ for(int k=i+1;k<j;k++){ if(gg[i][j]==1&&gg[i][k]==1&&gg[k][j]==1){ gg[i][j]=0; } } } } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(gg[i][j]){ g[j].push_back(i); } } } //#if(p[c[1]].size()==1) dp[1][0]=w[c[1]]; dp[1][1ll<<c[1]]=w[c[1]]; ans[1]=w[c[1]]; st[1].push_back(1ll<<c[1]); for(ll i=2;i<=n;i++){ ll now=c[i]; for(ll las:g[i]){//枚举上一个点 for(ll s:st[las]){//枚举上一个点的状态 if(s&(1ll<<now)){//上一个点就经过了这个公司 if(!dp[i].count(s)){ dp[i][s]=dp[las][s]; st[i].push_back(s); } dp[i][s]=max(dp[i][s],dp[las][s]); ans[i]=max(ans[i],dp[i][s]); } else{//上一个点没经过这个公司 ll t_now=s|(1ll<<now); if(!dp[i].count(t_now)){ st[i].push_back(t_now); } dp[i][t_now]=max(dp[i][t_now],dp[las][s]+w[now]); ans[i]=max(ans[i],dp[i][t_now]); } } } } for(int i=1;i<=n;i++) printf("%lld\n",ans[i]); return 0; }
优化2
// Problem: C. 连锁商店 // Contest: Codeforces - 2021年中国大学生程序设计竞赛女生专场 // URL: https://codeforces.com/gym/103389/problem/C // Memory Limit: 512 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; ll n,m,c[55],w[55]; vector<ll>g[55],p[55]; map<ll,ll>dp[55];//第i个商店状态j的最大值 vector<ll>st[55];///第i个商店有哪些状态 ll ans[maxn];///最大值 ll gg[55][55]; void del(int now){ vector<ll>tmp; for(int i=0;i<st[now].size();i++){ bool flag=1; for(int j=0;j<st[now].size();j++){ if(i==j) continue; if((st[now][i]|st[now][j])==st[now][j]){ flag=0;break; } } if(flag) tmp.push_back(st[now][i]); } st[now]=tmp; } int main(){ n=read,m=read; for(int i=1;i<=n;i++){ c[i]=read; p[c[i]].push_back(i); } rep(i,1,n) w[i]=read; for(int i=1;i<=m;i++){ ll u=read,v=read; g[v].push_back(u); } //#if(p[c[1]].size()==1) dp[1][0]=w[c[1]]; dp[1][1ll<<c[1]]=w[c[1]]; ans[1]=w[c[1]]; st[1].push_back(1ll<<c[1]); for(ll i=2;i<=n;i++){ ll now=c[i]; for(ll las:g[i]){//枚举上一个点 for(ll s:st[las]){//枚举上一个点的状态 if(s&(1ll<<now)){//上一个点就经过了这个公司 if(!dp[i].count(s)){ dp[i][s]=dp[las][s]; st[i].push_back(s); } dp[i][s]=max(dp[i][s],dp[las][s]); ans[i]=max(ans[i],dp[i][s]); } else{//上一个点没经过这个公司 ll t_now=s|(1ll<<now); if(!dp[i].count(t_now)){ st[i].push_back(t_now); } dp[i][t_now]=max(dp[i][t_now],dp[las][s]+w[now]); ans[i]=max(ans[i],dp[i][t_now]); } } } del(i); } for(int i=1;i<=n;i++) printf("%lld\n",ans[i]); return 0; }
碎碎念：
放到最后大概也没人看。赛时一直没想出正确思路，下午补题也是补了好久才补懂。优化1是张巨教的，优化2是看的submissons里的srly巨巨写的，反正也不是独立完成的，还是太菜了。
