[HNOI2005] 星际贸易 题解

[HNOI2005] 星际贸易

将问题分为两次 dp。

题面有:“只有一种获得最大贸易额的方法”

所以直接说明了贸易额与那些费用无关。

有考虑到无论干啥都要维护，第二次 \(dp\) 直接以暗物质为核心即可

对于这里 \(R\) 与 \(n*2\) 取 \(min\) 的一些细节理解。

我们设计状态，因为观察到了暗物质最多也就使用 \(n*2\) 个，与 \(R\) 如此之大的范围无关

第二次 \(dp\) 中，\(f_{i,j}\) 表示到了第 \(i\) 颗星球，还有 \(j\) 暗物质的最小花费

正确性：

• \(r > n*2\) 时，直接不买

• \(r \le n*2\) 时，做 \(dp\)，由大于 \(n*2\) 的位置转移过来是不合法的

对于第二次 dp 中，要进行销售的星球与要买暗物质的星球的维护费用冲突的解决

对于考虑暗物质是建立在确定了那些是要销售的星球的基础上的，所以第二次 \(dp\) 对于这些星球的维护费用不应该考虑。

由于我们用单调队列模拟这个滑动窗口的过程，当跑到被选为要销售的星球时，直接 \(head[j] = tail[j] = 0\)。

所以这里 \(dp\) 可以理解为在每两颗被选星球中间做选择。

CODE

#include<bits/stdc++.h>
#define print(a) cout<<#a"="<<(a)<<endl
#define debug() cout<<"Line:"<<__LINE__<<endl
#define sign() puts("-------")
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2010;
int n,m,r,L0;
int ans1,ans2;
bool mark[N];
int dp[N][N];
struct Star{ int goal,val,dis,price,cost; }a[N];
void DP(){
	memset(dp,-1,sizeof dp);
	dp[0][0] = 0;
	for(int i = 1;i<=n;++i)
		for(int j = 0;j<=m;++j){
			if(dp[i-1][j] >= 0)dp[i][j] = dp[i-1][j];
			if(j >= a[i].goal && dp[i-1][j-a[i].goal] >= 0)
				dp[i][j] = max(dp[i-1][j-a[i].goal] + a[i].val,dp[i][j]);
		}
	int res = 0;
	for(int i = 0;i<=m;++i){
//		print(dp[n][i]);
		if(dp[n][i] > dp[n][res])res = i;
	}
	for(int i = n,j = res;i;--i){
		if(dp[i][j] == dp[i-1][j])continue;
		else mark[i] = 1, j -= a[i].goal;
	}
//	print(res);
	ans1 = dp[n][res];
}
int f[N][N];
int tail[N],q[N][N],head[N];
void solve(){
	memset(f,0x3f,sizeof f);
	f[0][r] = 0;
	q[r][++tail[r]] = 0;
	for(int i = 1;i<=n;++i){
		for(int j = 0;j<=r;++j){
			if(a[i].price && j)f[i][j] = min(f[i][j],f[i][j-1] + a[i].price);
			if(tail[j+2] > head[j+2])f[i][j] = min(f[i][j],f[q[j+2][head[j+2]]][j+2] + a[i].cost);
			if(mark[i])head[j] = tail[j] = 0;
			while(head[j] < tail[j] && f[q[j][tail[j]-1]][j] >= f[i][j])--tail[j];
			q[j][tail[j]++] = i;
			while(head[j] < tail[j] && a[i+1].dis - a[q[j][head[j]]].dis > L0)++head[j];
		}
	}
	int res = 0;
	for(int i = 0;i<=r;++i)if(f[n][i] < f[n][res])res = i;
	if(f[n][res] == inf)puts("Poor Coke!");
	else printf("%d %d",ans1,ans1-f[n][res]);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&L0);
	r = min(r,n<<1);
	a[0] = {0,0,0,0,0};
	for(int i = 1;i<=n;++i)
		scanf("%d%d%d%d%d",&a[i].goal,&a[i].val,&a[i].dis,&a[i].price,&a[i].cost);
	for(int i = 1;i<=n;++i)if(a[i].dis - a[i-1].dis > L0)return puts("Poor Coke!"),0;
	DP();
	solve();
	return 0;
}