rockers(2).cpp

背包类问题浅析和一些背包类问题的解答源程序。

/*
ID:zhjshar1
PROG:rockers
LANG:C++
*/
#include <fstream>
using namespace std;

ifstream  in( "rockers.in" );
ofstream out( "rockers.out" );

int main(){
    int n, m, t, x, f[22][22]={0}, i, j, k, tem;
    in >>n >>t >>m;
    for( i=0; i<n; ++i ){
         in >>x;
         if( x > t ) continue;
         for( j=m; j>0; --j ){
              for( k=t; k>=x; --k ){
                   if( (tem=f[j][k-x]+1) > f[j][k] ) f[j][k] = tem;
              }
         }
         for( j=1; j<=m; ++j ){
              f[j][0] = f[j-1][t];
              for( k=1; k<x; ++k ){
                   if( f[j][k-1] > f[j][k] ) f[j][k] = f[j][k-1];
              }
         }
    }
    
    out <<f[m][t] <<endl;
    return 0;
}