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
",ans);
	}
	return 0;
}