HDU 2126 Buy the souvenirs(二)
sing namespace std; int a[35]; int dp[35][505]; int mark[35][505]; int main(){ int T; scanf("%d",&T); while(T--){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ mark[i][j]=1; } } for(int i=0;i<=n;i++){ dp[i][0]=0; } for(int i=0;i<=m;i++){ dp[0][i]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]; mark[i][j]=mark[i-1][j]; if(j>=a[i]){ if(dp[i-1][j-a[i]]+1>dp[i][j]){ dp[i][j]=dp[i-1][j-a[i]]+1; mark[i][j]=mark[i-1][j-a[i]]; } else if(dp[i][j]==dp[i-1][j-a[i]]+1){ mark[i][j]=mark[i-1][j]+mark[i-1][j-a[i]]; } } } } if(dp[n][m]) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",mark[n][m],dp[n][m]); else printf("Sorry, you can't buy anything.\n"); } return 0; }