题目意思是给你n节课,m天,接下来给出n行,每行有m个数,代表着第i节课学习j天能获得的价值。求能获得的最大价值。

递推式:dp[j] = max(dp[j], dp[j-k]+res[i][k])

意思就是学习j天的最大价值是当前价值,还是当前价值减去k天,用这k天来学习新的课程的价值。


代码:

StatusAccepted
Time93ms
Memory1772kB
Length705
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=105;
int res[maxn][maxn];
int dp[maxn];
int m, n;
inline int max(int a, int b){return a>b?a:b;}
int main()
{
    while(~scanf("%d%d", &n, &m)&&n+m){
        memset(res, 0, sizeof(res));
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d", &res[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=m;j>0;j--){
                for(int k=1;k<=j;k++){
                    dp[j]=max(dp[j], dp[j-k]+res[i][k]);
                }
            }
        }
        printf("%d\n", dp[m]);
    }
    return 0;
}