世间的黑暗力量被描述成一个长度为N 的非负整数序列{Ai}，每次它可以选择这个序列中的两个相邻的正整数，让他们的值同时减一并获得一点邪恶力量，直到不存在满足条件的数。
然而你不希望他能够得逞，所以你会使得他收集的能量尽可能少。
这个题目存在线性的dp，这里先说一种ΣAi的方法
我们设f[i][j][0/1]表示现在正在做第i位，这一位为j，前一位是否为0的最优解
显然我们不能在状态中保留连续的两个非零数
发现可以如下转移
f[i][j][0]=min({f[i-1][a[i]-j-k][1]+a[i]-j},f[i-1][a[i]-j][0]+a[i]-j)
f[i][j][1]=f[a[i]-j][0]+a[i]-j
这样在加上滚动数组即可
关于线性方法，我们设f[i]表示处理道第i位，且必须将第i位清零的答案
那么显然，不管第i位前后是否为0，我们都可以花Ai的代价将其清除（因为这样显然不是最优情况）
那么我们考虑可以从f[i-2]中转移过来，代价是ai
因为我们显然可以只讲ai清空而不管ai-1(从f[i-2]转移),也可以考虑清空ai和ai-1(从f[i-1])
我们还可以考虑从f[i-3]转移过来
这样必须清空a[i]和a[i-1]而不管a[i-2]
这样，最后的答案就是f[n+1]
方法1:code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 5000010
using namespace std;
int f[N][2],g[N][2],s[N],a[N],n,A=1<<30;
inline void gmin(int& x,int y){ x>y?x=y:0; }
int main(){
freopen("dark.in","r",stdin);
freopen("dark.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",a+i);
memset(f,0x3f,sizeof f);
memset(g,0x3f,sizeof f);
f[0][0]=s[0]=0;
for(int i=1;i<=n;++i){
for(int j=a[i-1]+1;j<=a[i];++j)
f[j][0]=f[j][1]=s[j]=0x3f3f3f3f;
for(int j=a[i];~j;--j) g[j][0]=g[j][1]=0x3f3f3f3f;
for(int j=a[i];~j;--j){
gmin(g[j][0],s[a[i]-j]+a[i]-j);
gmin(g[j][0],f[a[i]-j][0]+a[i]-j);
gmin(g[j][1],f[a[i]-j][0]+a[i]-j);
}
s[a[i]+1]=0x3f3f3f3f;
for(int j=a[i];~j;--j){
f[j][0]=g[j][0];
f[j][1]=g[j][1];
s[j]=min(s[j+1],f[j][1]);
}
}
A=f[0][0];
for(int i=0;i<=a[n];++i) gmin(A,f[i][1]);
printf("%d
",A);
}线性dp代码:
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,a[N],f[N];
int input() {
int f=1,g=0; char c=getchar();
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {g=(g<<3)+(g<<1)+c-'0';c=getchar();}
return f*g;
}
int main() {
freopen("dark.in","r",stdin);
freopen("dark.out","w",stdout);
n=input()+3;
for(int i=3;i<n;i++) a[i]=input();
for(int i=3;i<=n;i++)
f[i]=min(f[i-2]+a[i],f[i-3]+max(a[i-1],a[i]));
printf("%d
",f[n]);
return 0;
}