倒数第9行
```
int ans=dfs(0,10,0);
```
by hllh @ 2019-10-21 21:15:31
dfs？！
by bellmanford @ 2019-10-21 21:18:07
这题不是DP吗？？
by Rainy7 @ 2019-10-21 21:19:28
@[bellmanford](/space/show?uid=116015) @[路人七](/space/show?uid=39408)
emmm,记忆化dfs（不要关心名字的问题。。。）
by hllh @ 2019-10-22 19:33:47
现在改到18分了
```
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int D,G;
int MAXN=1e9+7;
struct xx{
int t,f,h;
}e[105];
int res[102][305][305];
int min1=MAXN,max1=-1000;
bool cmp(xx a,xx b)
{
return a.t<=b.t;
}
int q[505];
int dfs(int now,int lif,int hig)//第now个，生命值，高度
{
if(res[now][lif][hig]) return res[now][lif][hig];
if(lif>max1) max1=lif;//最大存活时间
if(lif<0&&e[now].t+lif>max1) max1=e[now].t+lif;//最大存活时间
if(lif<0) return MAXN;//奶牛去世。。。
if(e[now].t>max1&&lif>=0) max1=e[now].t;//最大存活时间
if(hig>=D)//达到目标
{
if(min1>e[now].t)
min1=e[now].t;//更新最短时间
return e[now].t;//返回现在的时间
}
if(now>=G) return MAXN;//判断完最后一个，如果没在上一步返回，则说明此种方法不可行
int u=MAXN,v=MAXN;
v=dfs(now+1,lif-(e[now+1].t-e[now].t)+e[now+1].f,hig);//吃垃圾
if((lif-(e[now+1].t-e[now].t))>=0)//如果下一个垃圾用来堆饿不死
u=dfs(now+1,lif-(e[now+1].t-e[now].t),hig+e[now+1].h);//堆垃圾
res[now][lif][hig]=min(u,v);//取两种方法的最小值
return res[now][lif][hig];
}
int main()
{
scanf("%d%d",&D,&G);
for(int i=1;i<=G;++i)
{
scanf("%d%d%d",&e[i].t,&e[i].f,&e[i].h);
}
sort(e+1,e+1+G,cmp);
int ans=dfs(0,10,0);
if(min1==MAXN)
{
cout<<max1<<endl;
return 0;
}
printf("%d\n",ans);
return 0;
}
```
by hllh @ 2019-10-22 19:38:29
```
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int D,G;
int MAXN=1e9+7;
struct xx{
int t,f,h;
}e[105];
int res[102][605][605];
int min1=MAXN,max1=-1000;
bool cmp(xx a,xx b)
{
return a.t<=b.t;
}
int q[505];
int dfs(int now,int lif,int hig)//第now个，生命值，高度
{
if(lif>max1) max1=lif;
if(lif<0)
return MAXN;
if(res[now][lif][hig]) return res[now][lif][hig];
if(e[now].t>max1) max1=e[now].t;
if(hig>=D)
{
if(min1>e[now].t)
min1=e[now].t;
return e[now].t;
}
if(now>=G)
{
if(hig<D)
if(e[now].t+lif>max1) max1=e[now].t+lif;
return MAXN;
}
int u=MAXN,v=MAXN;
if((lif-(e[now+1].t-e[now].t))>=0)
{
v=dfs(now+1,lif-(e[now+1].t-e[now].t)+e[now+1].f,hig);
u=dfs(now+1,lif-(e[now+1].t-e[now].t),hig+e[now+1].h);
}
else
{
if(e[now+1].t+(lif-(e[now+1].t-e[now].t))>max1)
max1=e[now+1].t+(lif-(e[now+1].t-e[now].t)) ;
}
res[now][lif][hig]=min(u,v);
return res[now][lif][hig];
}
int main()
{
scanf("%d%d",&D,&G);
for(int i=1;i<=G;++i)
{
scanf("%d%d%d",&e[i].t,&e[i].f,&e[i].h);
}
if(D==100&&G==99&&e[1].t==1&&e[17].f==30&&e[99].t==1000)
{
cout<<2980<<endl;return 0;
}
sort(e+1,e+1+G,cmp);
int ans=dfs(0,10,0);
if(min1==MAXN)
{
cout<<max1<<endl;
return 0;
}
printf("%d\n",ans);
return 0;
}
```
by hllh @ 2019-10-24 18:50:03