P2925 [USACO08DEC]干草出售Hay For Sale

Link

Solution

01背包（被某咕卡max()也太毒瘤了）

Code

#include<iostream>
const int maxn = 50000 + 10;
using namespace std;

int score[maxn], f[maxn], cost[maxn];

int main() {
    int c, h;
    scanf("%d%d", &c, &h);
    for (int i = 1; i <= h; i++)scanf("%d", &cost[i]);
    for (int i = 1; i <= h; i++)
        for (int j = c; j >= cost[i]; j--)
            f[j] = f[j] >= f[j - cost[i]] + cost[i] ? f[j] : f[j - cost[i]] + cost[i];
    printf("%d\n", f[c]);
    return 0;
}