题意
给定一个序列, 对于每一项有两种操作:
操作 1: 放置一个守卫塔, 耗费 \(a_i\)
操作 2: 放置一个木偶, 耗费为与右侧第一个守卫塔之间的距离.
求最小耗费.
思路
子状态 \(f[i]\) 表示在 \(i\)
状态转移方程显然为 \(f[i]=min(f[j]+a[i]+(i-j)*(i-j-1)/2)\).
- #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();
- }
来源: http://www.bubuko.com/infodetail-3156476.html