P2577 [ZJOI2005]午餐

题面: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
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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！