FZU Problem 2168 防守阵地 I

http://acm.fzu.edu.cn/problem.php?pid=2168

题目大意：

给定n个数和m,要求从n个数中选择连续的m个，使得a[i]*1+a[i+1]*2+……a[i+m]*m最大

思路：

常规思路是以每个数开始，枚举m个，但是这样会TLE。

可以有O（n)的算法。

例如样例的

n=5 m=3

五个数分别为

2 1 3 1 4

有三种连续的三个数

2 * 1 + 1 * 2 + 3* 3 = 13

1 * 1 + 3 * 2 + 1 * 3= 10

3 * 1 + 1 * 2 + 4 * 3 = 17

设sum[i]为到i的m个数的和，dp[i]为以i结束的m个数的乘积值。

则相邻两组间有关系，dp[i] =dp[i-1]-sum[i-1] + m*a[i] ；

例如第第二组的那个 dp[4 ]= dp[3]- sum[3] + 3 * 1 = 13-6+3*1=10

#include<cstdio>

const int MAXN=1000000+10;

int sum[MAXN],dp[MAXN],a[MAXN];

int main()

{

	int n,m;

	while(~scanf("%d%d",&n,&m))

	{

		sum[0]=0;

		dp[m]=0;

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

			scanf("%d",&a[i]);

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

		{

			sum[i]=sum[i-1]+a[i];

			dp[m]+=a[i]*i;

		}

		int ans=dp[m];

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

		{

			dp[i]=dp[i-1]-sum[i-1];

			dp[i]=dp[i]+m*a[i];

			sum[i]=sum[i-1]+a[i]-a[i-m];	

			if(ans<dp[i])

				ans=dp[i];

		}

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

	}

	return 0;

}

巴特西

FZU Problem 2168 防守阵地 I

最新文章

热门文章