UVA 473 - Raucous Rockers (dp)

題意
有n首歌，每首時長Ti，要把這n首歌裝進m個光盤裡面，每個光盤最多能存的時長為t
要求這些歌在光盤裡面要按照所給歌的先後順序存入，不能改變前後順序。
例如有4首歌，按順序給出他們的時長：1，2，3，4.
裝入一個容量時長為10的光盤裡， 可以是1，2，3或者1，3，4等，但是不能2，1，3
問最多能存幾首歌？

思路：
用f[i][j][k]表示前i首歌，用j個光盤，且第j個光盤用了k的時間，可存的最多首歌
當枚舉到第i首歌，用到第j個光盤時，有決策以及狀態轉移：

1. 選擇不要存這首歌，那麼有
   f[i][j][k] = max(f[i][j][k], f[i-1][j][k]);

2. 這首歌是第j個光盤的第一首歌時，有
   f[i][j][k] = max(f[i][j][k], f[i-1][j-1][t]+1);

3. 不是第j個光盤的第一首歌時
   f[i][j][k] = max(f[i][j][k], f[i-1][j][k-T[i]]+1);

/**===========================================
 *  This is a solution for ACM/ICPC problem.
 *
 *  @author: shuangde
 *  @blog: http://blog.csdn.net/shuangde800 
 *  @email: [email protected]
 *============================================*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MOD = 10007;

int n, t, m;
int T[MAXN];
int f[900][120][120];


int main(){

    int nCase;
    scanf("%d", &nCase);

    while(nCase--){
        
        scanf("%d%d%d", &n, &t, &m);
        int idx = 0, x;
        for(int i=1; i<=n; ++i){
            if(i==1) scanf("%d", &x);
            else scanf(", %d", &x);
            if(x <= t) T[++idx] = x; 
        }

        n = idx;

        memset(f, 0, sizeof(f));

        for(int i=1; i<=n; ++i){
            for(int j=1; j<=m; ++j){
                for(int k=0; k<=t; ++k){
                    f[i][j][k] = f[i-1][j][k];
                    if(k >= T[i]){
                        f[i][j][k] = max(f[i][j][k], f[i-1][j][k-T[i]]+1);
                        f[i][j][k] = max(f[i][j][k], f[i-1][j-1][t]+1);
                    }
                } 
            } 
        }
        printf("%d\n", f[n][m][t]);
        if(nCase) puts("");
    }

    return 0;
}

代碼君：