P1156 垃圾陷阱（dp）有待理解

2019-11-09 20:34:43

字体：大中小

来源：转载

供稿：网友

题见洛谷

#include<iostream>#include<cstdio>#include<cstring>#include<string> #include<algorithm>using namespace std;int deep,n,maxl=0,anst=999999;struct H{ int tim,tall,last;}st[200];int f[200];//高度为 i 的最大生命 int comp(const H & x,const H & y){ if(x.tim<y.tim)return 1; return 0;} int main(){ scanf("%d%d",&deep,&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&st[i].tim,&st[i].last,&st[i].tall); sort(st+1,st+n+1,comp); f[0]=10; for(int i=1;i<=n;i++) { int t=st[i].tim,l=st[i].last,h=st[i].tall; for(int j=deep;j>=0;j--) { if(f[j]>=t) { if(j+h>=deep){ PRintf("%d",t); return 0; } if(f[j+h]<f[j]) f[j+h]=f[j];//！！！！ f[j]+=l; } } } printf("%d/n",f[0]); return 0;}

上一篇：A1089. Insert or Merge (25)

下一篇：poj1936