学步园

因为同时有两个要求（数量最多、数量相同时长度最长），所以要维护两个数组。

因为T一定小于所有歌的长度的和，所以T上限是9678。不过如果T真的有10^9那么大应该如何处理？动态规划还适用吗？

我尝试用记忆化搜索WA了，很奇怪。换成递推就直接过了。

递推时，因为歌曲的出现顺序并不重要，所以在读取数据的时候，下标可以逆序从N-1到0，这样可以实现边读入边处理。如果歌曲顺序有要求的话，也可以换一下状态的定义，改为“dp(i,j)表示在时间 j 内唱前 i 首歌，最多可以唱多少首”（原本是 i 到N-1），和书中的0-1背包一样。

因为不需要打印解，滚动数组也可以。加上边读入边处理的优化，速度会稍微快一些。要注意内层循环的顺序。

滚动数组：Run Time: 0.039s

#define UVa  "LT9-5.12563.cpp"		//Jin Ge Jin Qu hao
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

//Global Variables. Reset upon Each Case!
const int maxn = 50 + 10, maxt = 10000;     //180 * n + 678 <= 180*50+678 = 9678 < 10000
int songs[maxn];
int dp[maxt];
int len[maxt];
int N, T;
/////

int main() {
    int K;
    scanf("%d", &K);
    for(int kase = 1; kase <= K; kase ++) {
        scanf("%d%d", &N, &T);
        for(int i = 0; i < maxt; i ++) {
            dp[i] = 1;
            len[i] = 678;
        }
        int song, ans = -1, anslen = -1;
        for(int i = 0; i < N; i ++) {
            scanf("%d", &song);
            for(int j = T; j >= 0; j --) {
                if(j > song) {
                    int tmp = dp[j - song] + 1;
                    if(tmp > dp[j]) {
                        dp[j] = tmp;
                        len[j] = len[j - song] + song;
                    }
                    else if(tmp == dp[j])
                        len[j] = max(len[j], len[j - song] + song);
                }
                if(ans < dp[j]) {
                    ans = dp[j];
                    anslen = len[j];
                }
                else if(ans == dp[j])
                    anslen = max(anslen, len[j]);
            }
        }
        printf("Case %d: %d %d\n", kase, ans, anslen);
    }
    return 0;
}

普通递推：Run Time: 0.053

#define UVa  "LT9-5.12563.cpp"		//Jin Ge Jin Qu hao
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

//Global Variables. Reset upon Each Case!
const int maxn = 50 + 10, maxt = 10000;     //180 * n + 678 <= 180*50+678 = 9678 < 10000
int songs[maxn];
int dp[maxn][maxt];
int len[maxn][maxt];
int N, T;
/////

int main() {
    int K;
    scanf("%d", &K);
    for(int kase = 1; kase <= K; kase ++) {
        scanf("%d%d", &N, &T);
 
        for(int i = 0; i < N; i ++) scanf("%d", &songs[i]);

        for(int i = 0; i < maxt; i ++) {
            dp[N][i] = 1;
            len[N][i] = 678;
        }
        for(int i = N - 1; i >= 0; i --) {
            for(int j = 0; j <= T; j ++) {
                dp[i][j] = dp[i+1][j];
                len[i][j] = len[i+1][j];
                if(j > songs[i]) {
                    int tmp = dp[i+1][j - songs[i]] + 1;
                    if(tmp > dp[i][j]) {
                        dp[i][j] = tmp;
                        len[i][j] = len[i+1][j - songs[i]] + songs[i];
                    }
                    else if(tmp == dp[i][j])
                        len[i][j] = max(len[i][j], len[i+1][j - songs[i]] + songs[i]);
                }
            }
        }
        printf("Case %d: %d %d\n", kase, dp[0][T], len[0][T]);
    }
    return 0;
}