题解 P2577 【[ZJOI2005]午餐】
Starria的脑残粉
2017-06-17 15:39:59
随机跳题跳到这题。。
其实就是个简单的dp辣,f[i][j]表示前i-1个数,第一个队列恰好要j的时间的最晚集合时间。
显然成立的是吃饭时间越长的越早打饭
然鹅200\*40000的好像开不下
降维呗、、
```cpp
#include<bits/stdc++.h>
using namespace std;
struct lsg{int x,y;}a[1000];
int n,f[400001],sum,ans,b[1000];
bool pd(lsg x,lsg y){return x.y>y.y;}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
sort(a+1,a+1+n,pd);memset(f,10,sizeof(f));f[0]=0;//排序而已
for (int i=1;i<=n;i++)b[i]=a[i].x+b[i-1];
for (int i=1;i<=n;i++){
for (int j=sum;j>=0;j--){
f[j+a[i].x]=min(f[j+a[i].x],max(f[j],a[i].y+j+a[i].x));//将i加入第一个队列
f[j]=max(f[j],a[i].y+b[i]-j);//将i加入第二个队列
}
sum+=a[i].x;
}
ans=1e9;
for (int i=1;i<=sum;i++)ans=min(ans,f[i]);
cout<<ans<<endl;
}
```