显然的DP，讲几个重要的地方
1.贪心：让吃饭时间长的先排队（证明从略）
2.状态：
f[i][j][k]代表前i个人，一号时间j，二号时间k显然MLE
所以压缩成f[i][j]代表前i个人，一号时间j，用前缀和维护时间，s[i]-j就是二号的时间
Code：
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct Person { 4 int take,eat; 5 bool operator < (Person ano)const { 6 return eat>ano.eat; 7 } 8 }p[233]; 9 int n,ans,s[233],f[233][233*233];//时间要开平方 10 inline void Init(){ 11 cin>>n; 12 for(int i=1;i<=n;i++)cin>>p[i].take>>p[i].eat; 13 sort(p+1,p+1+n);//贪心 14 //前缀和 15 for(int i=1;i<=n;i++)s[i]=s[i-1]+p[i].take; 16 memset(f,0x3f,sizeof(f)); 17 ans=0x3f3f3f3f; 18 f[0][0]=0; 19 } 20 inline void DP(){ 21 for(int i=1;i<=n;i++){ 22 for(int j=0;j<=s[i];j++){ 23 //去一号窗口 24 if(j>=p[i].take)f[i][j]=min(f[i][j],max(f[i-1][j-p[i].take],j+p[i].eat)); 25 //去二号窗口 26 f[i][j]=min(f[i][j],max(f[i-1][j],s[i]-j+p[i].eat)); 27 } 28 } 29 for(int i=0;i<=s[n];i++)ans=min(ans,f[n][i]); 30 cout<<ans<<endl; 31 } 32 int main(){//超简洁的main 33 Init(); 34 DP(); 35 return 0; 36 }