题解 P5638 【【CSGRound2】光骓者的荣耀】

Mophie · 2019-11-10 09:28:37 · 题解

update:修改了格式

这道题点进来的大佬 100% 都会做，这里给大家简述一些奇怪的做法......

Part1.水的不行的算法

先看一看这道题，他说了在第i个位置上可以选择跳到 i-k ~ i+k ;

那么我们只需要暴力枚举什么时候会跳即可，即枚举 i ，然后再往下做，时间复杂度 O(n^2m) 。

此算法竟然得 40 分。

Part2.part1的优化

再仔细看一眼题面，发现每一条路径非负，所以——

跳的越远越好

话说为什么非负就跳的越远越好呢？

即得易证显然
可见如上平凡
留作习题答案略
读者自证不难

所以每次即从 i 跳到 i+k 即可

时间复杂度为 O(n^2)

此算法得 80 分

Part3.1小小的优化

其实想到Part2就离Part3不远了（~~反正 80 分对我这种蒟蒻来讲足够了~~）

首先需要思考的是：我到底~~我是谁，我在哪，我在干什么~~是在算什么；

首先先枚举i，再算1->i的路径和，再计算i+k+1->n的路径和；

灵光一闪

其实不就是算 i+1->i+k 之间的距离与 1->n 之间的距离差嘛

所以只需枚举 i+1->i+k 即可，时间复杂度为 O(nk)

~~虽然一分也没有多拿到~~

Part3.2诡异的满分优化

由Part3得：枚举 i+1->i+k 即可；

那么上一个是 i->i+k-1 ;

只需上一个减去 i->i+1 加上 i+k-1->i+k 不就好了吗？

其时间复杂度为 O(n)

此算法得 100 分，代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000001],k,Max,now,cnt;
int main() 
{
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        cin>>a[i];
        cnt+=a[i];
    }
    for(int i=1;i<=k;i++)Max+=a[i],now+=a[i];
    for(int i=2;i<=n-k;i++)
    {
        now=now-a[i-1]+a[i+k-1];//i+1->i+k
        Max=max(Max,now);
    }
    cout<<cnt-Max<<endl;
    return 0; 
}

Part3.3前缀和优化

只需算 i+1->i+k 即可

那么即为 1->i+k 减去 1->i ;

自然而然的想到了前缀和优化

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long sum[1000001];
long long n,k;
int main()
{
    cin>>n>>k;
    if(k>=n-1)
    {
        cout<<0<<endl;
        return 0;
    } 
    for(int i=1;i<=n-1;i++)
    {
        long long x;
        cin>>x;
        sum[i]=sum[i-1]+x;//前缀和
    }
    long long cnt=sum[k];
    for(int i=2;i<=n-k;i++)
    {
        cnt=max(cnt,sum[i+k-1]-sum[i-1]);//i->i+k-1
    }
    cout<<sum[n-1]-cnt<<endl;
    return 0;
}

Part4：dp党的福利——万物皆可dp

话说此题 dp 也不难想

根据Part3可得每次跳k最优；

那么 dp 公式就出来了

$dp[i][1]$ 表示第i个跳则状态转移公式就出来了 $dp[i][0]=dp[i-1][0]+a[i]$; $dp[i][1]=dp[i-k][0]$$(i>=k)

再扫一遍即可~

故代码如下：

#include<bits/stdc++.h>
using namespace std;
long long dp[1000009][2],a[1000009],ans;
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n-1;i++)
    {
        cin>>a[i];
    }
    for(int i=2;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]+a[i-1];
        if(i>k)dp[i][1]=dp[i-k][0];
        dp[i][1]=min(dp[i-1][1]+a[i-1],dp[i][1]);//状态转移方程
    }
    cout<<dp[n][1]<<endl;//输出
    return 0;
}