# 如何证明决策单调性

### 方法一：（最简单实用的）打表

对于状态 i 和 j, 它们分别从 s[i] 和 s[j] 转移过来。那么这一类题目满足以下规律：$s[i]\textless=s[j](i\textless j)$

$$(j-i+Sigma(Ck)-L)^2(j\textless=k\textless=i)$$

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 100010

using namespace std;

int f[MX],s[MX],seq[MX],n,L, sum[MX];

void input()
{
scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++)scanf("%d",&seq[i]);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+seq[i];
}

void work()
{
for(int i=1;i<=n;i++)
{
f[i]=99999999;
for(int j=0;j<i;j++)
if(f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L)<f[i])
f[i]=f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L),s[i]=j;
}
cout<<f[n]<<endl;
for(int i=1;i<=n;i++)cout<<s[i]<<" ";
}

int main()
{
input();
work();
return 0;
}


#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 100010

using namespace std;
typedef long long ll;

int s[MX];
ll n,L,sum[MX],seq[MX],f[MX];

void input()
{
scanf("%lld%lld",&n,&L);
for(int i=1;i<=n;i++)scanf("%lld",&seq[i]);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+seq[i];
}

void work()
{
int j;
s[0]=0;
for(int i=1;i<=n;i++)
{
f[i]=999999999999999;
for(j=s[i-1];j<i;j++)
if(f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L)<f[i])
f[i]=f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L),s[i]=j;
}
cout<<f[n]<<endl;
}

int main()
{
input();
work();
return 0;
}


### 方法二：数学证明：

$$dp[k]+(f[i]-f[k]-c)^2<=dp[j]+(f[i]-f[j]-c)^2$$

$$dp[k]+(f[t]-f[k]-c)^2<=dp[j]+(f[t]-f[j]-c)^2$$

$$dp[k]+(f[i]+v-f[k]-c)^2<=dp[j]+(f[i]+v-f[j]-c)^2$$

$$2v(f[i]-f[k]-c)<=2v(f[i]-f[j]-c)$$

$$f[k]>=f[j]$$

现在没有问题了