[Uva12563] Jin Ge Jin Qu hao （完全背包，dp）

题目链接：https://vjudge.net/problem/UVA-12563

题意：n首歌要在m-1的时间内挑k首唱，现在希望在k尽可能大的情况下，时间尽可能长地唱。问最后最大k+1多大，最长时间+678多长。

普通完全背包，附加额外记一维记录歌曲个数。先判断当个数相同的时候，仅更新时长，否则两个都更新。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 55;
const int maxm = 11000;
int n, m, p;
int w[maxn], f[maxn][maxm][2];


signed main() {
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    int T, _ = 1;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
        m--;
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                f[i][j][0] = f[i-1][j][0];
                f[i][j][1] = f[i-1][j][1];
                if(j >= w[i]) {
                    if(f[i][j][1] == f[i-1][j-w[i]][1] + 1) {
                        f[i][j][0] = max(f[i][j][0], f[i-1][j-w[i]][0]+w[i]);
                    }    
                    else if(f[i][j][1] < f[i-1][j-w[i]][1] + 1) {
                        f[i][j][1] = f[i-1][j-w[i]][1] + 1;
                        f[i][j][0] = f[i-1][j-w[i]][0] + w[i];
                    }
                }
            }
        }
        printf("Case %d: %d %d
", _++, f[n][m][1]+1, 678+f[n][m][0]);
    }
    return 0;
}