UVA 473 - Raucous Rockers (dp)

本文は  http://blog.csdn.net/shuangde800
テーマゲート
に言及
还有,需要问一下n首の歌があって、毎首の時間はTiを成長して、このn首の歌をm個の光ディスクの中に入れて、毎光ディスクの最も多く貯蓄することができる時間はtになります
これらの歌はディスクの中で与えられた歌の前後順に保存され、前後の順序を変えることはできません.
例えば4曲あり、順番に時間を与える:1,2,3,4.
容量が10のディスクに入れると、1、2、3または1、3、4などですが、2、1、3はできません.
最大何曲まで保存できますか?
考え方:
前のi曲をf[i][j][k]で表し、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番目のCDの最初の曲でない場合
   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
", f[n][m][t]);
        if(nCase) puts("");
    }

    return 0;
}