01背包 Codeforces Round #267 (Div. 2) C. George and Job

题目传送门

 /*
题意:选择k个m长的区间,使得总和最大
01背包:dp[i][j] 表示在i的位置选或不选[i-m+1, i]这个区间,当它是第j个区间。
01背包思想,状态转移方程:dp[i][j] = max (dp[i-1][j], dp[i-m][j-1] + sum[i] - sum[i-m]);
在两个for循环,每一次dp[i][j]的值都要更新
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std; typedef long long ll;
const int MAXN = 5e3 + ;
const int INF = 0x3f3f3f3f;
ll a[MAXN];
ll sum[MAXN];
ll dp[MAXN][MAXN]; int main(void) //Codeforces Round #267 (Div. 2) C. George and Job
{
int n, m, k;
while (scanf ("%d%d%d", &n, &m, &k) == )
{
memset (sum, , sizeof (sum));
for (int i=; i<=n; ++i) {scanf ("%I64d", &a[i]); sum[i] = sum[i-] + a[i];} ll ans = ;
for (int i=m; i<=n; ++i)
{
ll tmp = sum[i] - sum[i-m];
for (int j=; j<=k; ++j)
{
dp[i][j] = max (dp[i-][j], dp[i-m][j-] + tmp);
}
ans = max (ans, dp[i][k]);
} printf ("%I64d\n", ans);
} return ;
} /*
5 2 1
1 2 3 4 5
7 1 3
2 10 7 18 5 33 0
*/
上一篇:人工神经网络入门(4) —— AFORGE.NET简介


下一篇:Codeforces Round #383 (Div. 2) D. Arpa's weak amphitheater and Mehrdad's valuable Hoses —— DP(01背包)