https://zybuluo.com/ysner/note/1238171
题面
给一个只包含({-1,0,1})的数列，每次操作可以让(a[i]+=a[i-1])，求最少操作次数使得序列单调不降。
- (nleq10^6)
解析
显然只能设状态(f[i][j])表示已处理完第(1-i)个数，第(i)个数转化为(j-1)的最小操作次数。
本题难度在于考虑转移条件。
话说我一开始是这么写的：（充分体现了我蒟蒻的本质)
fp(i,0,n) dp[i][0]=dp[i][1]=dp[i][2]=inf;
dp[1][a[1]+1]=1;
fp(i,2,n)
{
if(a[i]==-1)
{
dp[i][0]=dp[i-1][0];
//dp[i][1]=dp[i-1][2];
dp[i][2]=dp[i-1][2]+2;
}
if(a[i]==0)
{
dp[i][0]=dp[i-1][0]+1;
dp[i][1]=dp[i-1][1];
dp[i][2]=dp[i-1][2]+1;
}
if(a[i]==1)
{
dp[i][0]=dp[i-1][0]+2;
dp[i][1]=dp[i-1][0]+1;
dp[i][2]=dp[i-1][2];
}
}
re ll ans=min(dp[n][0],min(dp[n][1],dp[n][2]));
然后答案大了很多。
那应该怎样转移呢？
- 条件(1)：转化完后，前后二数应不降。
- 条件(2)：如果当前数不变，可接受前一数满足条件(1)的所有方案的最小值。
- 条件(3)：如果当前数变小，若前一数为(-1)，可接受符合条件(1)的所有方案；否则，只能接受(j=0)的方案。
- 条件(4)：如果当前数变大，若前一数为(1)，可接受符合条件(1)的所有方案；否则，只能接受(j=2)的方案。
至于一些细节如取(min)、对答案的贡献等自己想想吧。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define inf 1e18
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=1e6+100;
ll dp[N][3],n,a[N];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
int main()
{
n=gi();fp(i,1,n) a[i]=gi();
fp(i,0,n) dp[i][0]=dp[i][1]=dp[i][2]=inf;
dp[1][a[1]+1]=0;
fp(i,2,n)
{
if(a[i]==-1)
{
dp[i][0]=dp[i-1][0];
dp[i][1]=(a[i-1]==1)?min(dp[i-1][0],dp[i-1][1])+1:inf;
dp[i][2]=(a[i-1]==1)?min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+2:dp[i-1][2]+2;
}
if(a[i]==0)
{
dp[i][0]=dp[i-1][0]+1;
dp[i][1]=min(dp[i-1][1],dp[i-1][0]);
dp[i][2]=(a[i-1]==1)?min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1:dp[i-1][2]+1;
}
if(a[i]==1)
{
dp[i][0]=dp[i-1][0]+2;
dp[i][1]=(a[i-1]==-1)?min(dp[i-1][0],dp[i-1][1])+1:dp[i-1][0]+1;
dp[i][2]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]));
}
}
re ll ans=min(dp[n][0],min(dp[n][1],dp[n][2]));
if(ans>=inf) puts("BRAK");
else printf("%lld
",ans);
return 0;
}