ZJOI2005 午餐

动态规划

Luogu

显然每个队列按吃饭时间降序排列最优

那么就可以 dp 了

设 $dp(i,j,k)$ 为前 $i$ 个人，第一个队列打饭时间为 $j$ ，第二个队列为 $k$ 。因为 $j+k$ 是个定值，所以可以压成两维。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int INF = 0x3f3f3f3f;
const int MAXN = 200 + 5;
int N, Ans = INF;
int Dp[MAXN][MAXN * 200], Sum[MAXN];
struct Node
{
    int a, b;
} A[MAXN];
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
bool comp(Node x, Node y)
{
    return x.b > y.b;
}
int main()
{
    N = read();
    for(int i = 1; i <= N; ++i)
    {
        A[i].a = read();
        A[i].b = read();
    }
    std::sort(A + 1, A + 1 + N, comp);
    for(int i = 1; i <= N; ++i) Sum[i] = Sum[i - 1] + A[i].a;
    memset(Dp, INF, sizeof(Dp));
    Dp[0][0] = 0;
    for(int i = 1; i <= N; ++i)
    {
        for(int j = 0; j <= Sum[i]; ++j)
        {
            if(j >= A[i].a) Dp[i][j] = std::max(Dp[i - 1][j - A[i].a], j + A[i].b);
            Dp[i][j] = std::min(Dp[i][j], std::max(Dp[i - 1][j], Sum[i] - j + A[i].b));
        }
    }
    for(int i = 0; i <= Sum[N]; ++i) Ans = std::min(Ans, Dp[N][i]);
    printf("%d\n", Ans);
    return 0;
}