给出n个数字 1-8之间 要求选出来一个子序列 使里面1-8的数字个数 极差<=1 并且相同数字必须相邻(112 可以但是121不行)求这个子序列的最长长度
一道状压dp 看不懂别人的dp思想..自己造了一个出来..
首先枚举t 意义是 当前选取子序列 每个数字最少是多少 那么这个子序列中的数字个数为t t+1
dp[i][j]当前在i位 选取数字的情况压缩成j
枚举没选过的数字 用前缀和进行二分查找
从第i位开始 求出res使在满足i-res这个区间有t或者t+1的某数字 进行转移 更新dp[res][j|x]
当t为0的时候和t>0的时候 一个是 某种数字不选也可以 一个是每种数字都会被选择 所以分开来讨论
前者就是统计出现过的数字的种数
后者 当j|x为11111111 即每种数字都选完的时候 这时候才会满足 数字个数为t或者t+1 才可以进行对ans的更新
时间复杂度 n^2 * (255) * log(n)
一道题补了两天...期间打了好久游戏...QAQ
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
#include<malloc.h>
using namespace std;
#define L long long
int n ;
int dp[1050][(1<<8) + 5];
int a[1050];
int b[(1<<8) + 5];
int sum[1050][9];
int main(){
scanf("%d",&n);
memset(sum,0,sizeof(sum));
int ans = 0;
int mj = (1<<8) - 1;
for(int i=0;i<=mj;i++){
int z = i;
b[z] = 0;
while(z){
if(z%2 == 1)b[i] ++;
z/=2;
}
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
for(int j=1;j<=8;j++)sum[i][j] = sum[i-1][j];
sum[i][a[i]] ++ ;
}
for(int i=1;i<=8;i++){
if(sum[n][i]>0)ans++;
}
for(int t=1;t*8<=n;t++){
memset(dp , -1 ,sizeof(dp));
dp[0][0] = 0;
for(int i=0;i<n;i++){
for(int j=0;j<=mj;j++){
if(dp[i][j] == -1)continue;
for(int k=1;k<=8;k++){
int z = (1<<(k-1));
if((z&j) == 0){
int g=(z|j);
int l = i+1;
int r = n;
int res = -1;
while(l<=r){
int mid =(l+r)/2;
if(sum[mid][k] - t > sum[i][k]){
r = mid - 1;
}
else if(sum[mid][k] - t < sum[i][k]){
l = mid + 1;
}
else {
r = mid - 1;
res = mid;
}
}
if(res != -1){
if(dp[res][g] == -1 || dp[res][g] < dp[i][j] + t){
dp[res][g] = dp[i][j] + t;
if(b[g] == 8)
ans = max(dp[res][g] , ans);
}
}
l = i+1;
r = n;
res = -1;
while(l<=r){
int mid =(l+r)/2;
if(sum[mid][k] - t - 1> sum[i][k]){
r = mid - 1;
}
else if(sum[mid][k] - t - 1< sum[i][k]){
l = mid + 1;
}
else {
r = mid - 1;
res = mid;
}
}
if(res != -1){
if(dp[res][g] == -1 || dp[res][g] < dp[i][j] + t + 1){
dp[res][g] = dp[i][j] + t + 1;
if(b[g] == 8)
ans = max(dp[res][g] , ans);
}
}
}
}
}
}
}
printf("%d\n",ans);
}