CDOJ 876 爱管闲事 DP

爱管闲事

春希非常爱管闲事，他每天都会抽空帮助一些同学，由于春希非常死板，出于公平性，春希不会先帮助后来找他的同学。

现在有n个同学需要他的帮助，虽然他很想一天之类帮助所有人，但毕竟精力有限，于是他决定分m天来帮助他们。

根据事情的重要性，春希帮助不同同学会有不同的快乐值，而春希获得的总的快乐值为每天获得的快乐值的乘积。

现在给出n和m，以及帮助完各同学时获得的快乐值，求春希能获得的最大快乐值。

Input

第一行为一个整数T，代表数据组数。

每组数据，第一行两个整数n,m。表示需要帮助的同学的数量，和天数。(1≤m≤min(n,10),1≤n≤20)

第二行为n个整数，表示帮助这个同学的获得的快乐值，每个快乐值不大于5。

Output

每组数据输出一行，一个整数，表示最大的快乐值。

Sample input and output

Sample Input	Sample Output
1 5 3 3 2 1 4 5	125

Source

2014 UESTC Training for Dynamic Programming

 

题解：设定dp[i][j] 前i个 划分为j份 的答案

　　　dp[i][j] = max{dp[k][j-1] * (sum[i] - sum[k])}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long ll;

const int N=55;
int a[N],dp[N][N],sum[N],m,n;
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++) {
            scanf("%d",&a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        for(int i = 1; i <= n; i++) dp[i][1] = a[i] + dp[i-1][1];
        for(int j = 2; j <= m; j++) {
            for(int i = j; i <= n; i++) {
                for(int k = j-1; k < i ; k++) dp[i][j] = max(dp[i][j],dp[k][j-1] * (sum[i] - sum[k]));
            }
        }
        printf("%d
",dp[n][m]);
    }
    return 0;
}