你有一个长为 的序列 ,一开始全部为 ,你现在可以以任意顺序进行任意次以下两种操作:
- 选定整数 与不下降非负整数序列 ,对所有 ,令 加上 。
- 选定整数 与不上升非负整数序列 ,对所有 ,令 加上 。
问最少进行多少次操作使得 。
,。
对于这种和单调性有关的情况,一般考虑差分序列。那么设 。
考虑只有一种操作怎么做,显然两种操作是对称的,所以只用考虑第一种操作。不难发现第一种操作相当于把 都加上任意非负整数, 把 减去任意非负整数。而我们的目的是让 ,所以答案即为 。
同理,只有第二种操作时的答案为 。
考虑设 表示第一种操作让 增加了多少(),则答案为 。
设 表示确定完 且 的前 项的答案,不难发现对于同一个 , 越大 越小,而转移时 越小 转移到 的代价越小。注意到对于同一个 , 最多只有三种取值,那么记录下这三种取值的值和最小的 即可转移。
时间复杂度 ,代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int S=200005,inf=1e9;
int n,a[S];
int f[S][3],g[S][3];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=a[n+1]=0;
f[0][0]=0,g[0][0]=0;
f[0][1]=g[0][1]=inf;
f[0][2]=g[0][2]=inf;
for(int i=1;i<=n+1;i++)
{
int y[7],dp[7]={inf,inf,inf,inf,inf,inf,inf};
for(int j=0;j<3;j++) y[j]=a[i]-a[i-1]+f[i-1][j];
for(int j=3;j<6;j++) y[j]=f[i-1][j-3];
y[6]=0;
for(int j=0;j<7;j++)
{
int v=y[j];
if(v<0||v>a[i]) continue;
for(int k=0;k<3;k++)
{
int u=f[i-1][k];
if(u<0||u>a[i-1]) continue;
dp[j]=min(dp[j],g[i-1][k]+(u>v)+(a[i-1]-u<a[i]-v));
}
}
int id[7]={0,1,2,3,4,5,6};
sort(id,id+7,[&](int a,int b){return dp[a]<dp[b]||(dp[a]==dp[b]&&y[a]<y[b]);});
int p=0;
for(int j=0;j<7&&p<3;j++)
{
int k=id[j];
if(p==0||dp[k]!=g[i][p-1])
{
f[i][p]=y[k],g[i][p]=dp[k];
p++;
}
}
for(int j=p;j<3;j++) f[i][j]=g[i][j]=inf;
}
printf("%d\n",g[n+1][0]);
return 0;
}
// (y[i]>y[i+1])+(a[i]-y[i]<a[i+1]-y[i+1])