nyoj--1184--为了肾六（动态规划+滚动数组）

为了肾六

时间限制：4000 ms | 内存限制：210535 KB

难度：2

描述

最近肾六很流行，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

样例输出

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define MAXN 100010

long long sum[MAXN],num[MAXN];

long long  dp[2][MAXN];

int main()

{

	int m,n,k;

	while(scanf("%d%d%d",&n,&m,&k)!=EOF)

	{

		long long  ans=0;

		memset(sum,0,sizeof(sum));

		memset(dp,0,sizeof(dp));

		memset(num,0,sizeof(num));

		for(int i=1;i<=n;i++)

		{

			scanf("%lld",&num[i]);

			sum[i]=0;ans+=num[i];

			if(i<m) continue;

			for(int j=i;j>i-m;j--)

			sum[i]+=num[j];

		}

		if(n==k||m==n)

		{

			printf("%lld\n",ans);

			continue;

		}

		memset(dp,0,sizeof(dp));

		ans=0;

		for(int j=1;j<=k;j++)

		{

			for(int i=j*m;i<=n;i++)

			{

				dp[j&1][i]=max(dp[j&1][i],dp[j&1][i-1]);

				dp[j&1][i]=max(dp[j&1][i],dp[(j-1)&1][i-m]+sum[i]);

				ans=max(ans,dp[j&1][i]);

			}

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

nyoj--1184--为了肾六（动态规划+滚动数组）

为了肾六

最新文章

热门文章