Mayflyyh
Mayflyyh
MayFlyyh's Blog
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
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 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

本文链接:http://www.mayflyyh.com/archives/312
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
没有标签
首页      DP      HDU 5603 D Game
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

HDU 5603 D Game
> 给一个公差集合{D},再给N个数 > 1.在当前剩下的有序数组中选择X(X>=2) 个数字 > 2.检查1选择的X个数字是否构成等差数列,且公差∈{D} ; > 3.如果2满足,删除这X个数字 > 4.…
扫描二维码继续阅读
2018-08-14