【UOJ#495】新年的促销

题目

当了数天的快乐颓废人，之后就啥也不会了；

有一个简单的dp，设(dp_{i,j,k,p})表示前(i)个物品，花费了(j)元，购买了(k)个，白嫖了(p)个；转移的话考虑当前物品是买、白嫖、还是不买也不嫖；复杂度是(O(n^3m))的，显然过不去；

考虑对于一组物品，我们如何判断用一定钱数是否能买下它们；

显然我们需要按照价格排序，之后先买便宜的物品，能买多少就尽量买多少；买到不能买了，再康康能否把剩下的物品全部白嫖即可；

即按照价格排序从小到大排序之后最优方案存在一点(k)，满足(ileq k)的物品，都是买或不买；对于(i>k)的物品，都是白嫖或不嫖；

于是简单搞两个dp，(f_{i,j,k})表示前(i)个物品花(j)元买(k)个的最大收益，(g_{i,j})表示从(i)到(n)物品中价值前(j)大的物品价值和；我们枚举一下分界点(k)就好了；

代码

#include<bits/stdc++.h>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=305;
struct sth{int w,v;}a[maxn];
inline int cmp(const sth &A,const sth &B){return A.v<B.v;}
int n,m,A,B;
int g[maxn][maxn],dp[2][maxn][1005],ans[1005];
int main() {
	n=read(),m=read(),A=read(),B=read();
	for(re int i=1;i<=n;i++)a[i].w=read();
	for(re int i=1;i<=n;i++)a[i].v=read();
	std::sort(a+1,a+n+1,cmp);
	memset(g[n+1],-20,sizeof(g[n+1]));g[n+1][0]=0;
	for(re int i=n;i;--i) 
		for(re int j=0;j<=n-i;++j) {
			g[i][j]=max(g[i][j],g[i+1][j]);
			g[i][j+1]=max(g[i][j+1],g[i+1][j]+a[i].w);
		}
	int o=0;
	memset(dp,-20,sizeof(dp));
	dp[0][0][0]=0;
	for(re int i=1;i<=n;i++,o^=1) {
		for(re int j=0;j<i;++j)
			for(re int k=0;k<=m;k++) {
				dp[o^1][j][k]=max(dp[o^1][j][k],dp[o][j][k]);
				if(k+a[i].v<=m)
					dp[o^1][j+1][k+a[i].v]=max(dp[o^1][j+1][k+a[i].v],dp[o][j][k]+a[i].w);
			} 
		for(re int j=0;j<=i;++j) {
			int t=min(j/A+j/B,n-i);
			for(re int k=1;k<=m;k++)
				ans[k]=max(dp[o^1][j][k]+g[i+1][t],ans[k]);
		}
	}
	for(re int i=1;i<=m;i++) printf("%d ",ans[i]=max(ans[i],ans[i-1]));puts("");
	return 0;
}