fzu 防守阵地 1

#include<stdio.h>#include<string.h>#define rr 1000000int a[rr+5],sum[rr+5],ssum[rr+5];int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        sum[0]=ssum[0]=0;        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);        for(int i=1;i<=n;i++)        {            sum[i]=sum[i-1]+a[i];        }        for(int i=1;i<=n;i++)        {            ssum[i]=ssum[i-1]+sum[i];        }        long long ans=0;        for(int i=m;i<=n;i++)        {            long long mid=0;            long long cha=ssum[i-1]-ssum[i-m-1];            mid=sum[i]*m-cha;            if(mid>ans)                ans=mid;        }        PRintf("%lld/n",ans);    }}
处理前缀和
sum【1】=a[1]
sum[2]=a[1]+a[2];
sum[3]=a[1]+a[2]+a[3];
sum[4]=a[1]+a[2]+a[3]+a[4]
以样例为主
max=a[3]+2*a[4]+3*a[5];
a[5]=sim[5]-sum[4];
a[4]+a[5]=sum[5]-sum[3];
a[3]+a[4]+a[5]=sum[5]-sum[2];
max=(a[3]+a[4]+a[5])+(a[4]+a[5])+(a[5]);
=3*sum[5]-（sum[4]+sum[3]+sum[2]）
为了节省时间我们对sum进行意思前缀和
ssum【i-1】-是ssum【i-m-1】；
防守阵地 I
 FAQ | About | Google Group | Discuss | Author