題面:https://www.luogu.org/problem/P2577

本題一旦設出f[i][j]表示前i個人，在1號窗口打飯總時間j，最早吃完飯的時間 那么就很容易想到 當把i放在1號窗口 f[i][j] = min(f[i][j], max(f[i-1][j-s[i].a], j+s[i].b)) f[i-1][j-s[i].a]即第i個人吃飯+打飯時間<=前i-1人吃完飯的時間 j+s[i].b即第i個人吃飯+打飯時間>前i-1人吃完飯的時間 當把i放在2號窗口 f[i][j] = min(f[i][j], max(f[i-1][j], sum[i]-j+s[i].b)); 注意這里需要維護一個前綴和,然后就可以用sum[i]-j表示在2號窗口打飯總時間了.Code: #include<bits/stdc++.h> using namespace std; const int N = 210; int f[N][N*N]; struct node {int a, b;bool operator <(node z) const{return b>z.b;} }s[N]; int sum[N]; int main() {int n;scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d %d", &s[i].a, &s[i].b);sort(s+1, s+1+n);for(int i = 1; i <= n; i++)sum[i] = sum[i-1] + s[i].a;memset(f, 127, sizeof(f));f[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j <= sum[i]; j++){if(j>=s[i].a) f[i][j] = min(f[i][j], max(f[i-1][j-s[i].a], j+s[i].b));f[i][j] = min(f[i][j], max(f[i-1][j], sum[i]-j+s[i].b));}}int ans = 2147483647;for(int i = 0; i <= sum[n]; i++)ans = min(ans, f[n][i]);printf("%d\n", ans);return 0; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11567180.html

總結

以上是生活随笔為你收集整理的P2577 [ZJOI2005]午餐的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。