题解 P2034 【选择数字】

Creeper_LKF

2017-08-03 10:23:31

Solution

跑的最快的程序(43ms)+我也不知道是什么的优化+读入优化 原理:可以很容易的发现,原来的dp方程就是一直加(其实没有方程),然后限制了k个之后一个点a[I]可能会向前连续加j(j<=k)个然后停止,然后累加上前面获取的最大值,并且j的选取对前面dp[x<j]的答案无影响。 所以dp方程应该是dp[I]=max(dp[I-j]+a[j+1]+...+a[I]),其中J<=k,转化为前缀和就是dp[I]=max(dp[I-j]+sum[I]-sum[I-j+1]),为了方便计算,将j定义为第j个数,所以得到dp[I]=max(dp[j-1]+sum[I]-sum[j]),分析方程,发现sum[i]固定,即dp[i]=sum[i]+max(dp[j-1]-sum[j])。 那么我们需要每次都枚举j吗?那样会超时,所以肯定不需要。还记得我们上面说的吗?后面的j的取值对j之前的dp值无影响,而sum[j]固定,所以我们维护一个dp[j-1]+sum[j]的最大值位置pos,可以记录我们遇到的最大值和其位置,然后每次新计算出一个数时直接把新数的dp[I-1]-sum[I]拿给最大值比较、更新,然后当记录的位置“过期“(即pos<I-k时),重新计算pos。这样就可以省去大部分计算。当然还可以维护其它的数据结构来加速选择pos。 代码如下: ```cpp #include<bits/stdc++.h> #define INF 4611686018427387904L using namespace std; typedef long long LL; LL n,k,sum[100001],dp[100001]; inline char get_char(){//超级读入优化 static char buf[2000001],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,2000001,stdin),p1==p2)?EOF:*p1++; } inline LL read(){ LL num=0; char c; while(isspace(c=get_char())); while(isdigit(c)) num=num*10+c-48,c=get_char();//不压代码换速度 return num; } int main(){ n=read(),k=read(); LL maxn=-INF,pos,ns; for(int i=1;i<=n;++i) sum[i]=sum[i-1]+read(); for(int i=1;i<=k;++i){//前k个是可以直接选的(n==k时有效) dp[i]=sum[i]; if((ns=dp[i-1]-sum[i])>=maxn) maxn=ns,pos=i; } for(int i=k+1;i<=n;++i){ if(pos<i-k){//当过期时 maxn=-INF;//注意所有数组都要是long long的 for(int j=pos+1;j<=i;++j){//汇编代码友好 if((ns=dp[j-1]-sum[j])>=maxn){ maxn=ns,pos=j; } } } else { if((ns=dp[i-1]-sum[i])>=maxn) maxn=ns,pos=i;//寄存器友好(不开O2) } dp[i]=dp[pos-1]+sum[i]-sum[pos]; } printf("%lld",dp[n]); return 0; } ```