ZOJ - 3956 Course Selection System——01背包變形

There are n courses in the course selection system of Marjar University. The i-th course is described by two values: happiness Hi and credit Ci. If a student selects m courses x1, x2, ..., xm, then his comfort level of the semester can be defined as follows:

Edward, a student in Marjar University, wants to select some courses (also he can select no courses, then his comfort level is 0) to maximize his comfort level. Can you help him?

題意：有n個物品，每個物品有兩個價值hi與ci，每個物品可以選或者不選，求可獲得的最大價值和，價值和的計算方式題目中已經給出

思路：把價值和存入空間，然後dp求解哪些狀态是可行的，最終周遊一下價值和，找出最大的可行狀态即可，可惜價值和太大了，數組根本存不下。

然而我們發現雖然價值之和存不下，但是c的總和不過50000，是可以存下的，是以可以從c的總和入手，因為對于一個c的總和sumc，若想讓價值和最大，那麼sumh應該最大（如果不明白為什麼就先預設，一會兒會解釋），是以我們定義dp【i】【j】表示選到第i個物品時，sumc為j的最大sumh，注意一定保證dp【i】【j】是一個可行狀态（也就是說sumc一定可以被題目中的資料湊出來），狀态轉移方程為dp【i】【j】=max（dp【i-1】【j】，dp【i-1】【j-c【i】】+h【i】），一定要保證dp【i-1】【j-c【i】】是一個可行狀态，這樣dp【i】【j】才是一個可行狀态。

最終結果就是周遊一遍所有可行狀态，求dp【i】*dp【i】-dp【i】*i-i*i的最大值，注意用longlong

至于對于一個特定的sumc，為什麼要選最大的sumh，根據題目中的式子畫出圖像就可以看出，y大于0、x大于0的部分

是單調遞增的，而y小于0或者x小于0的部分是沒有意義的，特别注意沒有y大于0、x大于0單調遞減的情況

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 5e4+5;

int h[505], c[505], dp[maxn];

int main() {
    int T, n; scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        scanf("%d", &n);
        int sum = 0;
        for (int i = 1; i <= n; i++) { scanf("%d %d", &h[i], &c[i]); sum += c[i]; }
        for (int i = 1; i <= sum; i++) dp[i] = -INF;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = sum; j >= c[i]; j--) {
                if (dp[j-c[i]] == -INF) continue;
                dp[j] = max(dp[j], dp[j-c[i]] + h[i]);
            }
        }
        long long ans = 0;
        for (int i = 1; i <= sum; i++) {
            if (dp[i] == -INF) continue;
            ans = max(ans, (long long)dp[i]*dp[i]-(long long)dp[i]*i-(long long)i*i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}