题目大意
给定一个序列an，序列中只有1~8的8个整数，让你选出一个子序列，满足下列两个要求
1.不同整数出现的次数相差小于等于1
2.子序列中整数分布是连续的，即子序列的整数必须是1,1,1....1，2,2,2.....2,2.......连续分布
做法：
那么我们可以二分不同整数出现的次数，假如说二分出现次数是L，那么可以证明有a个整数出现次数是L，有(8-a)个整数出现次数是L-1（同时不难证明L+1比L更优)
这样每个整数只有两种状态，要么选L个，要么选L-1个。
压缩决策s，s的第i位表示是否对整数i做出了决策
再用容器把每一个不同整数出现的序列记录下来，这样就可以进行dp了
设dp[i][s]表示从原序列扫到前i个数，已经做出了s的决策，出现L次的不同整数个数最大是多少
枚举对第k个整数做决策，dp[i][s]就可以转移到另外两个状态
dp[next(k, L-1)][s|(1<<k)] = max(itself, dp[i][s]);
dp[next(k, L)][s|(1<<k)] = max(itself, dp[i][s]+1);
其中next(k, L)是指从i开始，往后的第L个k的整数位置
然后取dp[1~n][(1<<8)-1]中的最大值，返回答案即可
另外如果最大值小于等于0（注意等于！！），说明不存在解，返回0即可。
需要注意的是，当l = 2都不可行的时候需要特判处理。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 1111; const int inf = 1e9; int dp[maxn][1<<8], a[maxn], cur[maxn], n; vector <int> in[10]; int can(int L) { for(int i = 1; i <= 8; i++) cur[i] = 0; memset(dp, 128, sizeof(dp)); dp[1][0] = 0; for(int i = 1; i <= n; i++) { for(int s = 0; s < (1<<8); s++) { if(dp[i][s] < 0) continue; for(int k = 1; k <= 8; k++) { if(s & (1<<(k-1))) continue; if(in[k].size() - cur[k] < L-1) continue; dp[in[k][cur[k] + L - 2]][s|(1<<(k-1))] = max(dp[in[k][cur[k] + L - 2]][s|(1<<(k-1))], dp[i][s]); if(in[k].size() - cur[k] < L) continue; dp[in[k][cur[k] + L - 1]][s|(1<<(k-1))] = max(dp[in[k][cur[k] + L - 1]][s|(1<<(k-1))], dp[i][s]+1); } } cur[a[i]]++; } int ans = -inf; for(int i = 1; i <= n ; i++) ans = max(ans, dp[i][(1<<8) - 1]); if(ans <= 0) return 0; return ans * L + (8 - ans)*(L-1); } int main() { //freopen("a.txt", "r", stdin); cin>>n; for(int i = 1; i <= n; i++) cin>>a[i]; for(int i = 1; i <= n; i++) in[a[i]].push_back(i); int l = 2, r = n, ans = -inf; while(l < r) { int mid = (l+r)>>1; if(can(mid)) l = mid+1; else r = mid; } if(can(2) == 0) { ans = 0; for(int i = 1; i <= 8; i++) if(in[i].size() > 0) ans++; cout<<ans<<endl; } else { ans = max(can(l), can(l-1)); cout<<ans<<endl; } }