[文章目录]
Description
fox来到了一排葡萄架下,葡萄架上有很多葡萄(n串),它想将一部分葡萄偷走.
每串葡萄都有一个价值,当然,由于有酸有甜,葡萄的价值可能为正,也可能为负.
当然,为了让农夫看不出来,fox规定,每连续的k串葡萄中,它最多选b串,但是由于fox是比较贪心的,每连续k串葡萄中,它会最少选a串.
现在,fox要选出一些葡萄,而农夫得到剩余的葡萄,由于fox有嫉妒心理,希望让fox得到的价值减去农夫得到的价值的差值最大
对于100%数据 n<=10000,0<=a<=b<=k<=10
冬令营原题，不过印象中一直是拿什么单调队列解题，后来才知道是状压DP。。。
先找到所有可行状态，然后存到一个数列里，然后通过每一个可行状态向下DP，（据说有人直接拿前一个状态更新现在的状态，但是会有一个问题就是可能前一个状态根本都不成立）。然后就很简单的DP下去就好了。
不过，WA了
问题出在问题的文字游戏上，连续k个？？？n<k的时候呢？哈哈哈，之前处理出的状态都没有用啊。就直接不管状态就好了。。。哈哈哈。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Mi 0xefefefef
using namespace std;
int n,k,a,b,sum,col[2000],num[2000],cnt,ans=-1<<30;
bool v[2000];
int w[10100];
int f[11000][1100];
int work(int x)
{
int re=0;
while(x) re+=x&1,x>>=1;
return re;
}
int doit(int x)
{
int re=0;
for(int i=1;i<=k;i++)
if(x&(1<<i-1)) re+=w[i];
return re;
}
int main()
{
memset(f,0xef,sizeof(f));
scanf("%d%d%d%d",&n,&k,&a,&b);
for(int i=0;i<(1<<k);i++)
{
int tmp=work(i);
if(tmp>=a&&tmp<=b) col[++cnt]=i,v[i]=1;
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]),sum+=w[i];
if(n<k)
{
for(int i=1;i<=n;i++)
if(w[i]>0) ans+=w[i];
printf("%d",(ans<<1)-sum);
return 0;
}
for(int i=1;i<=cnt;i++) f[k][col[i]]=doit(col[i]);
for(int i=k;i<n;i++)
for(int j=1;j<=cnt;j++)
{
if(f[i][col[j]]==Mi) continue;
int tmp=(col[j]>>1);
if(v[tmp]) f[i+1][tmp]=max(f[i+1][tmp],f[i][col[j]]);
if(v[tmp|(1<<k-1)]) f[i+1][tmp|(1<<k-1)]=max(f[i+1][tmp|(1<<k-1)],f[i][col[j]]+w[i+1]);
}
for(int i=1;i<=cnt;i++)
ans=max(ans,f[n][col[i]]);
printf("%d",(ans<<1)-sum);
return 0;
}