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