HDU 5603 D Game

给一个公差集合{D}，再给N个数
1.在当前剩下的有序数组中选择X（X>=2) 个数字

2.检查1选择的X个数字是否构成等差数列，且公差∈{D} ;

3.如果2满足，删除这X个数字

4.重复1-3，直到不能删除更多数字

问最多可以删除多少个数字？

N<=300

一眼看去十分复杂，难点1在检验一串数字是否为等差数列，难点2在删除一段数字后，左右两边段合在一起的能不能尽量再删

不应该埋头考虑上面的问题。

观察等差数列性质，可以得知：任何一个长度大于等于4的等差数列，都可以通过长度为2或者长度为3的等差数列一段一段合并。

再加上这个数据范围很接近区间DP，我们便设DP[i][j]表示该区间能否被全部删完

预处理长度为2和3的数组

对于长度大于等于四的子段有两种情况：

一种是dp[i+1][j-1]刚好可以被删完，且(a[j]-a[j])∈{D}，则dp[i][j]也可以全部删完

另一种是枚举k，检验a[i],a[k],a[j]能否构成等差数列且公差在集合D中，然后再看dp[i+1][k-1]与dp[k+1][j-1]能否被全部删完，注意考虑边界(k=i+1与k=j-1)的情况

最后用F[i]表示现在到i最多能删F[i]个

如果1~i能删完，那么F[i]=i

否则F[i]=max(F[i],F[j],dp[j+1][i]*(i-j+1);

CODE:

#include<bits/stdc++.h>
inline int read(){
    int x=0,flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*flag;
}
int a[1000],f[1000],dp[1000][1000];
std::set<int> s;
int main(){
    int T=read();
    while(T--){
        s.clear();
        memset(f,0,sizeof(f));
        memset(dp,0,sizeof(dp));
        int n=read(),m=read();
        for(int i=1;i<=n;++i) a[i]=read();
        while(m--) s.insert(read());
        for(int i=1;i<=n;++i){
            dp[i+1][i]=1;
            dp[i-1][i]=s.count(a[i]-a[i-1]);
            if(i>=3)
                dp[i-2][i]=s.count(a[i]-a[i-1])&((a[i]-a[i-1])==(a[i-1]-a[i-2]));
        }
        for(int i=4;i<=n;++i){
            for(int l=1,r=l+i-1;r<=n;l++,r=l+i-1){      
                if(dp[l+1][r-1])
                    dp[l][r]|=s.count(a[r]-a[l]);
                for(int d=l;d<r;++d)
                    dp[l][r]|=dp[l][d]&dp[d+1][r];
                for(int d=l+1;d<=r-1;++d)
                    if((a[r]-a[d]==a[d]-a[l]))
                        if(s.count(a[r]-a[d]))
                            dp[l][r]|=dp[l+1][d-1]&dp[d+1][r-1];
            }
        }
        int ans=0;
        for(int i=1;i<=n;++i){
            f[i]=f[i-1];
            if(dp[1][i]){
                f[i]=i;
                continue;
            }
            for(int j=1;j<=i-1;++j){
                if(dp[j][i])
                    f[i]=std::max(f[i],f[j-1]+i-j+1),ans=std::max(ans,f[i]);
            }
        }
            printf("%d\n",f[n]);
    }
}