「Bzoj 1899」「Zjoi2004」Lunch 午餐 (贪心+DP)

BZOJ 1899
题意：见上。
本题无法直接 DP，所以我们想到贪心方案，吃饭慢的排前面打饭，按照这个方法来进行排序后就可以DP了。
可以设$dp(i,j)$为前$i$个人在1号打饭花了$j$时间的最小吃饭时间。
转移：
$i$安排到1号：$dp(i,j)=max(dp(i-1,j-a_i),j+b_i)$
$i$安排到2号：$dp(i,j)=max(dp(i-1,j),sum_i-j+b_i)$
其中$sum_i=\sum_{j=1}^ia_j$
初值$dp(0,0)=0$，其他为$INF$
知识点：这种无法直接DP也无法直接贪心的题目可以贪心后DP做，并且如果DP的维度太大需要根据性质尝试合并维度或者删除维度。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 200 + 5, INF_ = 1000000000;

struct data {
    int a, b;
}pp[MAXN];

int n, dp[MAXN][MAXN * MAXN], sum[MAXN];

bool cmp(const data &x, const data &y) {return x.b > y.b;}

void clean() {
    sum[0] = 0;
} 
int solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d%d", &pp[i].a, &pp[i].b);
    std::sort(pp + 1, pp + 1 + n, cmp);

    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + pp[i].a;
    for (int i = 0; i <= n; i++) 
    for (int j = 0; j <= sum[n]; j++) dp[i][j] = INF_;
    dp[0][0] = 0;

    int ans = INF_;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum[i]; j++) {
            if (j >= pp[i].a) dp[i][j] = std::min(dp[i][j], std::max(dp[i - 1][j - pp[i].a], j + pp[i].b));
            dp[i][j] = std::min(dp[i][j], std::max(dp[i - 1][j], sum[i] - j + pp[i].b));
            if (i == n) ans = std::min(ans, dp[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}