一个关于背包省去一维的问题
  • 板块P1156 垃圾陷阱
  • 楼主y_dove
  • 当前回复16
  • 已保存回复16
  • 发布时间2020/6/19 17:12
  • 上次更新2023/11/7 00:23:11
查看原帖
一个关于背包省去一维的问题
248872
y_dove楼主2020/6/19 17:12

rt,蒟蒻代码如下,如果去掉第一维就会错(即把g[i][j]改成g[j])可是倒序循环01背包不是可以去掉第一维吗,为什么会错啊?求大佬解释

/*垃圾陷阱*/ 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 1e4 + 10;
int g[1010][1010];
int read(){
	char ch = getchar();
	int x = 0;
	while(ch < '0' || ch > '9')		ch = getchar();
	while(ch >= '0' && ch <= '9')	x = x * 10 + ch - 48,ch = getchar();
	return x;
}
struct Rab{
	int t,f,h;
	bool operator <(Rab A){
		return t < A.t;
	}
}r[maxn];
int main()
{
	int D = read(),G = read();
	for(int i = 1; i <= G; ++i){
		scanf("%d%d%d",&r[i].t,&r[i].f,&r[i].h);
	}
	sort(r+1,r+G+1);
	memset(g,0xcf,sizeof(g));
	int ans = 0;
	g[0][0] = 10;
	for(int i = 1; i <= G; ++i){
		for(int j = 2 * D; j >= 0; --j){	
			if(g[i-1][j] - (r[i].t - r[i-1].t) >= 0)
				g[i][j] = g[i-1][j] + r[i].f - (r[i].t - r[i-1].t);
			if(j >= r[i].h && g[i-1][j - r[i].h] - (r[i].t - r[i-1].t) >= 0)
				g[i][j] = max(g[i][j],g[i-1][j-r[i].h] -  (r[i].t - r[i-1].t));
			if(j >= D && g[i][j] >= 0){
				printf("%d\n",r[i].t);
				return 0;
			}
			if(g[i][j] >= 0){
				ans = max(ans,r[i].t + g[i][j]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}
2020/6/19 17:12
加载中...