题解 P6040 课后期末考试滑溜滑溜补习班

题解-P6040 「ACOI2020」课后期末考试滑溜滑溜补习班

题目意思

题目较长，不便于描述

$Sol$

这道题目就是考察了一道基础的单调队列优化 $Dp$ ，以及化柿子的方法。

$20ptc$ ，暴力 $Dp$

设 $f_{i}$ 表示到 $i$ 的最小花费精力，转移 $O(n^2)$ 即可 $f_i=min\{f_j+(i-j-1)*d+k+a_i\},j∈[i-x,i-1)$

$Code1$

if(n<=1000)
{
    memset(f,127/3,sizeof(f));
    f[1]=a[1];
    for ( int i=2;i<=n;i++ ) 
        for ( int j=max(1ll,i-X);j<i;j++ ) 
            f[i]=min(f[i],f[j]+K+(i-j-1)*D+a[i]);
    printf("%lld\n",f[n]);
    exit(0); 
}

$100ptc$ ，单调队列优化 $Dp$

对于上述柿子我们可以进行移项合并得到： $f_i=a_i+k+(i-1)*d+min\{f_j-j*d\}$

到这里我们很容易想到用单调队列去维护 $f_j-j*d$ 单减即可，于是就是单调队列的基本操作了。

$Code2$

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e7+5;

int n,m,K,D,X,type,a[N],f[N],q[N],Seed;

inline int read() 
{
    int sum=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) 
        sum=sum*10+(ch^48),ch=getchar();
    return sum;
}

inline int rnd () 
{
    static const int MOD = 1e9;
    return Seed=(1ll*Seed*0x66CCFF%MOD+20120712)%MOD;
}

inline void Sub()
{
    for ( int i=1;i<=n;i++ ) a[i]=read();
    if(n<=1000)
    {
        memset(f,127/3,sizeof(f));
        f[1]=a[1];
        for ( int i=2;i<=n;i++ ) 
            for ( int j=max(1ll,i-X);j<i;j++ ) 
                f[i]=min(f[i],f[j]+K+(i-j-1)*D+a[i]);
        printf("%lld\n",f[n]);
        exit(0); 
    }
    f[1]=a[1];
    int head=1,tail=1;
    q[1]=1;
    for ( int i=2;i<=n;i++ ) 
    {
        while(head<=tail&&i-q[head]>X) head++;
        f[i]=f[q[head]]+K+(i-q[head]-1)*D+a[i];
        while(head<=tail&&f[q[tail]]-q[tail]*D>=f[i]-i*D) tail--;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    exit(0);
}

inline void Sub1()
{
    Seed=read();
    for ( int i=1;i<=n;i++ ) a[i]=rnd();
    f[1]=a[1];
    int head=1,tail=1;
    q[1]=1;
    for ( int i=2;i<=n;i++ ) 
    {
        while(head<=tail&&i-q[head]>X) head++;
        f[i]=f[q[head]]+K+(i-q[head]-1)*D+a[i];
        while(head<=tail&&f[q[tail]]-q[tail]*D>=f[i]-i*D) tail--;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    exit(0); 
}

signed main() 
{
    n=read();
    K=read();
    D=read();
    X=read();
    type=read();
    if(!type) Sub();
    else Sub1();
    return 0;
}
/*
10 30630 56910 2 0
7484 99194 86969 17540 29184 68691 91892 81564 93999 74280 

717318
*/