状态A
状态：d[i][j] 已经第i首歌还剩j时间，还能最多唱几首
决策：唱或不唱 1)d[i][j]-->d[i+1][j-song[i]] ;2)d[i][j]-->d[i+1][j] ;
选择：最大的但j>0的
int dp(int i,int j)
{int& ans=d[i][j];if(d[i][j]>=0) return ans;ans=-1;if(i==n) ans=0;else{if(j>song[i]) ans=dp(i+1,j-song[i])+1;ans=max(ans,dp(i+1,j));}return ans;
}int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=0;i<n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); int ans=dp(0,t);int ans_t;for(int j=1;j<=t;j++) if(d[n][j]!=-1) { //能走到n点的且t为最小的 ans_t=j;break;}printf("Case %d: %d %d\n",++kase,ans+1,t-ans_t+Jin);}return 0;
} int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=0;i<n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); int ans_t;for(int i=n;i>=0;i--)for(int j=0;j<=t;j++){int& ans=d[i][j];if(i==n) ans=0;else{ans=-1;if(j>song[i]) ans=d[i+1][j-song[i]]+1;ans=max(ans,d[i+1][j]);}}
// for(int i=n;i>=0;i--) //测试输出d[i][j]的值
// {
// for(int j=0;j<=t;j++)
// cout<<d[i][j]<<' ';
// cout<<endl;
// }printf("Case %d: %d %d\n",++kase,a[0][t]+1,t-ans_t+Jin);}//难打印时间，因为d[0][60~100]都为1; return 0;
}
状态B
状态：d[i][j] 已经第i首歌用时j时间，还能最多唱几首
决策：唱或不唱 1)d[i][j]-->d[i+1][j+song[i]] ;
2)d[i][j]-->d[i+1][j] ;
选择：最大的但j<t的
int dp(int i,int j)
{int& ans=d[i][j];if(d[i][j]>=0) return ans;ans=-1;if(i==n) ans=0;else{if(j+song[i]<t) ans=dp(i+1,j+song[i])+1;ans=max(ans,dp(i+1,j));}return ans;
}int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=0;i<n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); int ans=dp(0,0);int ans_t;for(int j=t-1;j>=0;j--) if(d[n][j]!=-1) {ans_t=j;break;}printf("Case %d: %d %d\n",++kase,ans+1,ans_t+Jin);}return 0;
}
2）递推法
int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=0;i<n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); int ans_t;for(int i=n;i>=0;i--)for(int j=0;j<=t;j++){int& ans=d[i][j];if(i==n) ans=0;else{ans=-1;if(j+song[i]<t) ans=d[i+1][j+song[i]]+1;ans=max(ans,d[i+1][j]);}}
// for(int i=n;i>=0;i--)
// {
// for(int j=0;j<=t;j++)
// cout<<d[i][j]<<' ';
// cout<<endl;
// }//难打印时间，因为d[0][0~40]都为1;
// printf("Case %d: %d %d\n",++kase,ans+1,ans_t+Jin);}return 0;
} 状态C
状态：d[i][j] 从第i首歌起，用了j时间，最多能唱几首
决策：唱或不唱 1)d[i][j]-->d[i+1][j+song[i]] ;
2)d[i][j]-->d[i+1][j] ;
选择：最大的但j<t的
1）记忆化搜索
int dp(int i,int j)
{int& ans=d[i][j];if(d[i][j]>=0) return ans;ans=-1;if(i==n+1) ans=0;else{if(j+song[i]<t) ans=dp(i+1,j+song[i])+1;ans=max(ans,dp(i+1,j));}return ans;
}
int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); int ans=dp(1,0),ans_t;for(int i=t-1;i>=0;i--)if(d[n+1][i]!=-1) {ans_t=i;break;}printf("Case %d: %d %d\n",++kase,ans+1,ans_t+Jin);}return 0;
}
2）递推法
int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); for(int i=n+1;i>=0;i--)for(int j=0;j<=t;j++){int& ans=d[i][j];if(i==n+1) ans=0;else{ans=-1;if(j+song[i]<t) ans=d[i+1][j+song[i]]+1;ans=max(ans,d[i+1][j]);}}
// for(int i=n;i>=1;i--)
// {
// for(int j=0;j<=t;j++)
// cout<<d[i][j]<<' ';
// cout<<endl;
// }
// printf("Case %d: %d %d\n",++kase,ans+1,ans_t+Jin);}return 0;
}
状态：d[i][j] 从第i首歌起，j时间内，最多能唱几首
决策：唱或不唱 1)d[i][j]-->d[i+1][j-song[i]] ;
2)d[i][j]-->d[i+1][j] ;
选择：最大的但j>0的
1）记忆化搜索
int dp(int i,int j)
{int& ans=d[i][j];if(d[i][j]>=0) return ans;ans=-1;if(i==n+1) ans=0;else{if(j-song[i]>0) ans=dp(i+1,j-song[i])+1;ans=max(ans,dp(i+1,j));}return ans;
}
int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); int ans=dp(1,t),ans_t;for(int i=0;i<t;i++)if(d[n+1][i]!=-1) {ans_t=i;break;}printf("Case %d: %d %d\n",++kase,ans+1,t-ans_t+Jin);}return 0;
} 2）递推法
int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); for(int i=n+1;i>=0;i--)for(int j=0;j<=t;j++){int& ans=d[i][j];if(i==n+1) ans=0;else{ans=-1;if(j-song[i]>0) ans=d[i+1][j-song[i]]+1;ans=max(ans,d[i+1][j]);}}
// for(int i=n;i>=1;i--)
// {
// for(int j=0;j<=t;j++)
// cout<<d[i][j]<<' ';
// cout<<endl;
// }
// printf("Case %d: %d %d\n",++kase,ans+1,ans_t+Jin);}return 0;
} 下面是相反的定义，从1到n
状态：d{i][j] 前i首歌，用时j最多唱了几首
状态转移：1) d[i][j]-->d[i-1][i-song[i]]+1
2) d[i][j]-->d[i-1][j];
状态选择：最大的
int main()
{int T,kase=0;scanf("%d",&T);while(T--){scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)scanf("%d",&song[i]);memset(d,-1,sizeof(d)); for(int i=0;i<=n;i++) for(int j=0;j<=t;j++){int& ans=d[i][j];if(i==0) ans=0;else{ans=-1;if(j-song[i]>0) ans=d[i-1][j-song[i]]+1;ans=max(ans,d[i-1][j]); }}cout<<d[n][t];
// printf("Case %d: %d %d\n",++kase,ans+1,ans_t+Jin);}return 0;
}
但递推法的都不知道怎么求出最大用时，可能是状态定义的不好