dp[i][j]表示前i门课在j天内所能获得的最大收益
转移方程
dp[i][j]=Max(dp[i-1][j-k]+A[i][k])
注意优化空间时迭代的方向(多重背包和0/1背包的区别)
#include<iostream> #include<cstring> #define Max(a,b) (a<b?b:a) using namespace std; int N,M; int A[101][101]; int dp[101]; //决定前i门课,使用j天所能获得的最大收益 //dp[i][j]=dp[i-1][j-k]+A[i][k] int main(){ while(cin >> N >> M && (N || M)){ for(int i = 1; i <= N; i++){ for(int j = 1; j <= M; j++){ cin >> A[i][j]; } } memset(dp,0,sizeof(dp)); for(int i = 1; i <= N; i++){ for(int j = M; j >= 1; j--){ for(int k = 1; k <= j; k++){ dp[j] = Max(dp[j-k]+A[i][k],dp[j]); } } } cout << dp[M] << endl; } return 0; }