题解 CF743E 【Vladik and cards】

``` 贡献一篇题解（由于这道题我水挂了，掉进了巨坑） 其实这就是一道状压dp+二分答案（还是那句话，想到就挺简单） 但是还是要分析分析的： 这道题首先要想到，我们提取出的子序列中任意一个数都是连在一块的 （就是坨在一块儿的），那么这些数字中夹杂的其他数字也就是作废了。 假设我们要在“1,2,3,1,2,1,3,3,1”中提取出3个1， 1. 我们可以选择“ **1** ,2,3, **1** ,2, **1** ,3,3,1”这三个加粗的1，那么“2,3,2”就被作废了，不能用了， 2. 我们也可以提取“**1** ,2,3, **1** ,2,1,3, **1** ”中这三个不连续、不紧凑的1呢？ 那么我们浪费的其他数字显然更多了（2,3,3,2,3,3），所以明显前者更优，然后我们只需要开个向量存每个数字的位置（当然是升序存的）， 计算得出当前点后面添上的数字串的末尾所处的位置，以及一系列的操作后就可以完成dp的推导了。 ``` ```cpp #include<bits/stdc++.h> #define M 1010 using namespace std; inline int read(){ int x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x; } int n,ans; int x[M],num[10]; int f[M][(1<<8)+10]; vector<int> at[10]; bool check(int tim){ //check函数，ans在这里更新 memset(num, 0 ,sizeof(num)); //每次清零 memset(f , 250 , sizeof(f)); //每次变成-inf f[0][0]=0; int tot=-0x3f3f3f3f; for(int i=0;i<n;++i){ //线性推i for(int j=0;j<(1<<8);++j) if(f[i][j]>=0) //枚举状态 for(int k=0;k<8;++k){ //枚举当前位后接下来要添上的tim个数字k if(j&(1<<k)) continue; int now=num[k]+tim-1; //计算得出k最后一位的位置 if(now<at[k].size()) f[at[k][now]][j|(1<<k)]=max(f[at[k][now]][j|(1<<k)],f[i][j]); if(++now<at[k].size()) f[at[k][now]][j|(1<<k)]=max(f[at[k][now]][j|(1<<k)],f[i][j]+1); } ++num[x[i]]; //将当前位在所处的向量数组中减去（相当于减去，也就是不能用了） } for(int i=0;i<=n;++i) tot=max(tot , f[i][(1<<8)-1]); if(tot<0) return false; //没有dp成功直接return false ans=max(ans , 8*tim+tot); //dp成功了ans就等于八倍的tim加上额外的个数 return true; } int main(){ n=read(); x[0]=9;//巨坑在这里，x0要变成9，不然check里i=0的时候。。。哎。。。栽这儿了 for(int i=1;i<=n;++i) x[i]=read()-1,at[x[i]].push_back(i); int l=0,r=n/8+1; for(int i=0;i<8;++i) //先对r做个优化（能说是剪枝么？） r=min(r,(int)at[i].size()); if(!r){ //特判，如果有任意一个数没出现过 for(int i=0;i<8;++i) if(at[i].size()) ++ans; printf("%d\n",ans); return 0; } while(l<=r){ //主函数很简短，主要就是二分 int mid=l+r>>1; if(check(mid)) l=mid+1; else r=mid-1; } printf("%d\n",ans); return 0; } ```