通过把f全部输出,发现在#2输出177时候恰好会有最大高度为100
by SHIROHA_NARUSE @ 2022-09-25 00:14:37
点二的测试样例
```
100 85
1 9 8
10 7 4
103 3 7
103 5 5
107 7 8
112 5 4
115 4 2
12 1 5
121 5 8
122 5 7
123 3 3
132 4 8
135 9 1
143 8 1
144 7 4
146 3 6
149 9 2
150 4 3
154 4 8
162 5 8
171 6 6
177 4 9
177 8 9
183 2 2
185 5 6
187 6 6
187 7 6
19 4 1
192 2 3
197 2 5
203 9 2
210 4 3
213 5 3
219 2 4
222 2 9
229 4 5
235 5 3
24 3 7
241 6 5
249 1 8
256 2 5
258 5 6
261 6 9
269 7 9
27 1 7
278 8 6
283 4 4
288 5 5
291 4 6
297 6 5
3 2 2
300 7 2
309 5 1
316 4 3
323 1 5
324 6 2
328 5 4
33 2 3
335 9 8
34 1 4
340 8 8
342 4 1
345 9 8
347 2 3
35 6 2
351 4 3
360 7 4
369 3 9
373 4 1
378 7 4
378 7 9
386 3 2
41 6 3
45 8 3
52 2 8
53 7 3
61 1 4
68 6 1
71 3 4
74 3 5
77 7 5
79 8 9
84 8 5
85 7 5
94 4 9
```
by SHIROHA_NARUSE @ 2022-09-25 00:15:43
尝试复现了下bug
这是和我同思路的AC代码:
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXG 105
#define MAXH 3050
using namespace std;
int d,g;
struct node{
int t,f,h;
}a[MAXG];
int f[MAXG][MAXH];
bool vis[MAXG][MAXH];
int chp[MAXG]={10};
int ans2=10;
bool cmp(node a,node b){
return a.t<b.t;
}
int main(){
scanf("%d%d",&d,&g);
for(int i=1;i<=g;i++)
scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);
sort(a+1,a+1+g,cmp);
for(int i=1;i<=g;i++)chp[i]+=chp[i-1]+a[i].f;
vis[0][10]=1;
for(int i=1;i<=g;i++){
for(int j=chp[i];j>=0;j--){
if(vis[i-1][j+a[i].t-a[i-1].t]){
f[i][j]=max(f[i][j],f[i-1][j+a[i].t-a[i-1].t]+a[i].h);
vis[i][j]=1;
}
if(vis[i-1][j+a[i].t-a[i-1].t]){
f[i][j+a[i].f]=max(f[i][j+a[i].f],f[i-1][j+a[i].t-a[i-1].t]);
vis[i][j+a[i].f]=1;
}
if(f[i][j]>=d){
printf("%d",a[i].t);
return 0;
}
}
}
for(int i=1;i<=g;i++){
if(ans2>=a[i].t)ans2+=a[i].f;
else break;
}
printf("%d",ans2);
return 0;
}
```
然后改动36~37行
```cpp
if(j+a[i].t-a[i-1].t-a[i].f>=0&&vis[i-1][j+a[i].t-a[i-1].t-a[i].f]){
f[i][j]=max(f[i][j],f[i-1][j+a[i].t-a[i-1].t-a[i].f]);
vis[i][j]=1;
}
```
则会出现最开始的输出177的情况
不太能理解为什么会这样,求大佬分析qwq
by SHIROHA_NARUSE @ 2022-09-25 17:36:22
草。
我们的代码惊人的相似。
by Oier_szc @ 2023-02-06 17:38:56
竟然连错的都一样。
by Oier_szc @ 2023-02-06 17:43:02
本蒟蒻一开始也是错得一模一样,并且与 lz 对那个 AC 代码进行更改后的代码思路几乎一样。代码如下:
```cpp
memset(f, -1, sizeof(f));
f[0][10] = 0;
for(int i = 1; i <= g; i++)
for(int j = 0; j <= 30*g+30; j++){
int t1 = j+a[i].ti-a[i-1].ti, t2 = t1-a[i].fi;
if(f[i-1][t1] != -1) f[i][j] = max(f[i][j], f[i-1][t1]+a[i].hi);
if(t2 >= 0) f[i][j] = max(f[i][j], f[i-1][t2]);
if(f[i][j] >= d) {printf("%d", a[i].ti); return 0;}
}
```
根据 lz 的这份 AC 代码,经过一晚上的调试,最终找到了问题。
通过输出 $f$,AC 代码的 $f[5][2] = 10$,是从 $f[4][6]$ 直接继承过来的;而本人的代码 $f[5][2] = 15$,是从 $f[4][5]$ 直接继承过来的。错误的这个继承所代表的是**所剩下的生命会随着时间流逝先变成负数**,再因为吃掉垃圾再次变成正的,这是不合题意的。
因此,将代码改为如下即可:
```cpp
memset(f, -1, sizeof(f));
f[0][10] = 0;
for(int i = 1; i <= g; i++)
for(int j = 0; j <= 30*g+30; j++){
int t1 = j+a[i].ti-a[i-1].ti, t2 = t1-a[i].fi;
if(f[i-1][t1] != -1) f[i][j] = max(f[i][j], f[i-1][t1]+a[i].hi);
if(t2 >= a[i].ti-a[i-1].ti) f[i][j] = max(f[i][j], f[i-1][t2]);
if(f[i][j] >= d) {printf("%d", a[i].ti); return 0;}
}
```
by David_Mercury @ 2023-03-11 09:03:13