显然的DP是，dp[i][j][val]

val是1e6的

简化

发现，其实决策很有限，最优解的i-1的val选择有限

这里的一个trick是，f[i][j][0]转移不考虑a[i]和a[i-1]的大小关系，如果不计算到j的话，只能更差，而且之后会有一种方案记录到

这样，保留了一种可能的a[i]>a[i-1]的0状态，所以后面1的转移就存在这种情况。

代码：

#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=5005;const int inf=0x3f3f3f3f;int f[N][N][3];int a[N];int n;int main(){    rd(n);    for(reg i=1;i<=n;++i) rd(a[i]);    memset(f,inf,sizeof f);    f[1][0][0]=0,f[1][1][1]=0;    for(reg i=2;i<=n;++i){        for(reg j=0;j<=(i+1)/2;++j){            f[i][j][0]=min(f[i-1][j][0],f[i-1][j][2]);            f[i][j][1]=min(f[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),f[i-1][j-1][2]+max(0,min(a[i-2]-1,a[i-1])-a[i]+1));            f[i][j][2]=f[i-1][j][1]+max(0,a[i]-a[i-1]+1);        }    }    for(reg k=1;k<=(n+1)/2;++k){        printf("%d ",min(f[n][k][0],min(f[n][k][1],f[n][k][2])));    }    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2019/2/22 21:32:02*/