题意： 给定一个字符串（只包含小写的前20个字母） 可以对任意指定区间进行一次翻转操作 问最长连续字符串长度使得不存在重复字符
题解： 只有二十种字符 所以很明显是一个状压dp
设置dp[i]表示 状态i的所有子集的最长长度 所以答案就是枚举所有状态： 该状态 + 该状态补集的子集
核心代码：
for(int i=0;i<(1<<20);i++)for(int j=0;j<20;j++)if(i&(1<<j))
dp[i]=max(dp[i],dp[i^(1<<j)]);
这里是一个状压dp的套路 每个状态都可以只从它的少一个元素的子集转移到它 因为从整体来看状态是从小到大遍历的 所以它的更少的子集已经转移到了它的少一个元素的子集
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+100; char s[N]; int dp[(1<<21)+10],ans,vis[21]; int main() { scanf("%s",s+1);int len=strlen(s+1); for(int i=1;i<=len;i++) { memset(vis,0,sizeof vis);int cnt=0,state=0; for(int j=i;j<=len;j++) { if(vis[s[j]-‘a‘])break; vis[s[j]-‘a‘]=1; cnt++;state|=(1<<(s[j]-‘a‘)); dp[state]=cnt; } } for(int i=0;i<(1<<20);i++)for(int j=0;j<20;j++)if(i&(1<<j)) dp[i]=max(dp[i],dp[i^(1<<j)]); for(int i=0;i<(1<<20);i++) ans=max(ans,dp[i]+dp[i^((1<<20)-1)]); cout<<ans; return 0; }
题解： dp[i] 表示放置了这个状态的位置的最小花费 然后往后面转移即可 注意一开始排序可以消去绝对值的影响 正确性和上一题一样 比他小的状态显然已经处理好了
还是很好的状压dp
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e6+10; vector<int>edge[30]; ll dp[1<<21]; int n,a[30],col[1<<21],m; int main() { for(int i=1;i<(1<<20);i++)col[i]=col[i-(i&-i)]+1; while(~scanf("%d%d",&n,&m)) { for(int i=0;i<(1<<n);i++)dp[i]=1e18;dp[0]=0; for(int i=0;i<n;i++)edge[i].clear(); for(int i=0;i<n;i++)scanf("%d",&a[i]);int l,r; while(m--)scanf("%d%d",&l,&r),l--,r--,edge[l].push_back(r),edge[r].push_back(l); sort(a,a+n); for(int j=0;j<=((1<<n)-2);j++) { for(int k=0;k<n;k++)if(!(j>>k&1)) { int cnt=0; for(auto v:edge[k]) if(j>>v&1)cnt++;else cnt--; dp[j+(1<<k)]=min(dp[j+(1<<k)],dp[j]+1ll*cnt*a[col[j]]); } } printf("%lld\n",dp[(1<<n)-1]); } return 0; }
原文：https://www.cnblogs.com/bxd123/p/11630052.html
