洛谷题解【爱与愁的心痛】

佚名 6年前 (2019-05-04) 随笔 1705人围观抢沙发百度已收录

题目传送门

思路

本题难度本为入门难度,因为他的数据很小,用O（n²）的暴力算法就可以AC,但是,作为一个对于认为自己水题过多而感到羞愧的OIer,我决定用O（n）的算法来做这道题.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我不打算用前缀和（其实就是不会），用前缀和也可以做出O（n）的时间复杂度，但是很复杂，而且常数因子还比我接下来要介绍的算法的常数因子大，所以，我自认为我的这个算法是洛谷全站最好的（我翻了题解）.

思想:贪心&动态规划

如果a[n]<a[m+1],那么a[n]~a[m]区间的和一定小于a[n+1]~a[m+1]区间的和.

而a[n+1]~a[m+1]区间的和减a[n]~a[m]区间的和就等于a[m+1]-a[n].

则用b[m+1]表示a[m+1]-a[n],那么a[n+2]~a[m+2]区间的和减a[n]~a[m]区间的和就等于a[m+1]-a[n]+a[m+2]-a[n+1]也就是b[m+1]+a[m+2]-a[n+1].而他的值又可以用b[m+2]表示

所以得到状态转移方程为:b[m+2]=b[m+1]+a[m+2]-a[n+1].

另外,若a[1]~a[m]就是最小的或n=m,则程序会出现错误,需要特判:

if(b[no]>0||n==m)//特判
        no=m;

剩下的就很简单了,直接上代码.

Code

#include <iostream>
#include <queue>
using namespace std;
long long n,m,gkmin=9999999999999999,ans,no;//我就是喜欢把gkmin设的大一点,你咬我啊
long long a[3002];
long long b[3002];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n-m;i++)
    {
        b[i+m]=b[i+m-1]+a[i+m]-a[i];//状态转移
        if(gkmin>b[i+m])
            gkmin=b[i+m],no=i+m;
    }
    if(b[no]>0||n==m)//特判
        no=m;
    for(int i=no;i>no-m;i--)
        ans+=a[i];
    cout<<ans;
     return 0;
}