终于会写DP了,这种水水的还是能写的~ 嘿嘿~
/* ID:bysen LANG:C++ PROG:rockers */ #include<stdio.h> using namespace std; int DP[21][21][21]; int time[21]; int N,T,M; int max( int a,int b ){ return a>b?a:b; } int getDP( int k,int t,int j ) { int ret=0; for( int i=0;i<j;i++ ) ret=max( DP[k][t][i],ret ); return ret; } int getCD( int cd,int k ) { int ret=0; for( int i=1;i<=T;i++ ) for( int j=0;j<k;j++ ) ret=max(ret,DP[cd][i][j] ); return ret; } int main() { freopen( "rockers.in","r",stdin ); freopen( "rockers.out","w",stdout ); scanf( "%d %d %d",&N,&T,&M ); for( int i=1;i<=N;i++ ) scanf( "%d",&time[i] ); for( int k=1;k<=M;k++ ) for( int i=1;i<=T;i++ ) for( int j=1;j<=N;j++ ) { if( i-time[j]==0) DP[k][i][j]=1; if( i-time[j]>=0 ) { if( (i-time[j])%T==0 ) DP[k][i][j]=max( DP[k][i][j],getCD(k-1,j)+1 ); else DP[k][i][j]=max( DP[k][i][j],getDP(k,i-time[j],j)+1 ); } } /* for( int k=1;k<=M;k++ ) { for( int i=1;i<=T;i++ ) { for( int j=1;j<=N;j++ ) printf( "%d ",DP[k][i][j] ); printf( "\n" ); } printf( "\n" ); }*/ int ans=0; for( int i=0;i<=T;i++ ) for( int j=0;j<=N;j++ ) ans=max( ans,DP[M][i][j] ); printf( "%d\n",ans ); }