[ZJOI]午餐 贪心+dp

这个题如果直接dp的话要考虑

先从题目类型入手，这种规划性问题 应该是个dp

1开始的时间、1结束的时间、2开始的时间、2结束的时间

这是200^6级别的状态数，且没有任何状态优化的余地

所以就要考虑使用特殊方法结合性质优化

然后手玩，发现打饭时间长的一定是在前面

所以可以排个序，然后利用 前面的人 非1即2的原理优化

所以1开始的时间设进状态，这样2开始的时间也就可以补出来，然后就可以更新了

码：

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;struct la{int x,y;}a[233];int f[2][50000],n,i,m,j,b[233],o,ans=1099999999;bool cmp(la a,la b){return a.y>b.y;}int main(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);}sort(a+1,a+1+n,cmp);for(i=1;i<=n;i++)b[i]=b[i-1]+a[i].x;for(i=0;i<=40000;i++)f[o^1][i]=f[o][i]=999999;f[o^1][0]=0;for(i=1;i<=n;i++,o^=1){for(j=0;j<=40000;j++){f[o][j+a[i].x]=min(f[o][j+a[i].x],max(f[o^1][j],j+a[i].x+a[i].y));f[o][j]=min(max(f[o^1][j],b[i]-j+a[i].y),f[o][j]);} for(j=0;j<=40000;j++)f[o^1][j]=999999;}for(i=1;i<=40000;i++)ans=min(ans,f[o^1][i]);printf("%d",ans);}