nyoj 1184 为了肾六 【dp】

描述

最近肾六很流行，goshawk看身边的朋友都用上了apple。自己还用着W年前的Samsung。于是决定去IT公司打工，都是为了肾六。现在上司让他解决下面的一个小问题，但是goshawk没学好算法，被这个问题难住了，聪明的你帮帮他吧。

给一个n个整数的序列p₁,p₂,p₃.....p_n。你要以下面的方式选k对整数。[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m),  为了让这个表达式的值尽可能大。赶快帮他解决这个问题吧。

输入

第一行包含三个整数n,m,和k(1 ≤ (m × k) ≤ n ≤ 5000)。第二行包含n个整数p1，p2,p3.....pn(0 ≤ pi ≤ 10^9).

输出

单行输出一个整数。最大和的值。

样例输入

5 2 11 2 3 4 57 1 32 10 7 18 5 33 0

样例输出

961

思路：dp[k][i]表示前i个数取k组得到的最大贡献。

dp[k][i] = max(dp[k][i-1], dp[k-1][i-M]+(a[i-M+1] + ...+a[i]))。

用滚动数组优化下就可以了。

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#define INF 0x3f3f3f
#define eps 1e-8
#define MAXN (5000+10)
#define MAXM (100000)
#define Ri(a) scanf("%d", &a)
#define Rl(a) scanf("%lld", &a)
#define Rf(a) scanf("%lf", &a)
#define Rs(a) scanf("%s", a)
#define Pi(a) printf("%d\n", (a))
#define Pf(a) printf("%.2lf\n", (a))
#define Pl(a) printf("%lld\n", (a))
#define Ps(a) printf("%s\n", (a))
#define W(a) while(a--)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define LL long long
#define lson o<<1, l, mid
#define rson o<<1|1, mid+1, r
#define ll o<<1
#define rr o<<1|1
using namespace std;
LL sum[MAXN], p[MAXN];
LL dp[2][MAXN];
int main()
{int N, M, K;while(scanf("%d%d%d", &N, &M, &K) != EOF){LL ans = 0;for(int i = 1; i <= N; i++){Rl(p[i]); sum[i] = 0; ans += p[i];if(i < M)continue;for(int j = i; j > i-M; j--)sum[i] += p[j];}if(N == K || M == N)//剪枝{Pl(ans);continue;}CLR(dp, 0); ans = 0;for(int k = 1; k <= K; k++){for(int i = k*M; i <= N; i++){dp[k&1][i] = max(dp[k&1][i], dp[k&1][i-1]);dp[k&1][i] = max(dp[k&1][i], dp[(k-1)&1][i-M]+sum[i]);ans = max(ans, dp[k&1][i]);}}Pl(ans);}return 0;
}