USACO Section 3.4 Raucous Rockers - 一道不错的DP

今天第二个1A的...~~~状态红上的说....这道题很典型的DP...而DP关键就是构造唯一的状态...我是用dp[i][j]表示用到了第i个唱片..并且第i个唱片用了j分钟...找到唯一状态..转移啥的就很简单了...我有个处理..就是用dp[i][0]表示用i-1个唱片最多能存下的歌曲数~~~

Program:

/* ID: zzyzzy12 LANG: C++ TASK: rockers */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long using namespace std; int N,T,M,dp[26][26],ans,x,i,j,k; int main() { freopen("rockers.in","r",stdin); freopen("rockers.out","w",stdout); scanf("%d%d%d",&N,&T,&M); memset(dp,-1,sizeof(dp)); dp[1][0]=0; ans=0; while (N--) { scanf("%d",&x); for (i=M;i>=1;i--) if (dp[i][0]>=0) break; for (;i>=1;i--) for (j=T-x;j>=0;j--) if (dp[i][j]>=0 && dp[i][j+x]<dp[i][j]+1) { dp[i][j+x]=dp[i][j]+1; if (dp[i][j+x]>dp[i+1][0]) dp[i+1][0]=dp[i][j+x]; if (dp[i][j+x]>ans) ans=dp[i][j+x]; } } printf("%d\n",ans); return 0; }