防御准备

题意

给定一个序列，对于每一项有两种操作：

• 操作1：放置一个守卫塔，耗费\(a_i\)

• 操作2：放置一个木偶，耗费为与右侧第一个守卫塔之间的距离。

求最小耗费。

思路

子状态\(f[i]\)表示在\(i\)

状态转移方程显然为\(f[i]=min(f[j]+a[i]+(i-j)*(i-j-1)/2)\)。

复杂度为\(n^2\)，显然不行。观察到只有\(i,j\)，考虑斜率优化。

\(end\)。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T> inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }
    template<typename T> inline void write (T x) {
        if (x<0) putchar('-'),x=-x;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Solve {
    #define int long long
    
    const int N=1000001;
    
    int n;
    int a[N],dp[N],q[N];
    int head,tail;
    
    inline double calc (int a,int b) {
        return (dp[b]+b*(b+1)/2.0-dp[a]-a*(a+1)/2.0)/(b-a);
    }
    
    inline void MAIN () {
        read(n);
        for (register int i=1; i<=n; ++i) {
            read(a[i]);
        }
        head=tail=1;
        for (register int i=1; i<=n; ++i) {
            while (head<tail&&calc(q[head],q[head+1])<i) ++head;
            dp[i]=dp[q[head]]+a[i]+(i-q[head])*(i-q[head]-1)/2;
            while (head<tail&&calc(q[tail-1],q[tail])>calc(q[tail],i)) --tail;
            q[++tail]=i;
        }
        write(dp[n]);
    }
    
    #undef int
}

int main () {
    Solve::MAIN();
}

防御准备

原文：https://www.cnblogs.com/ilverene/p/11357336.html