JDOJ-2171: Grape

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注