F.Sorting Pancakes

题意：
给你 $n(n\leq 250)$ 个整数的序列 $a(\sum a_i\leq250)$ ，你可以用 $1$ 的花费将 $a_i-1$ ，使 $a_{i+1}$ 或 $a_{i-1}\text{ }+1$ ，问最小用多少的花费可将序列变为不上升序列
思路：
由于本题数据范围极小，于是想到费用流，但是由于最终变换出来的序列未知，所以无法实现
于是考虑对于每一个 $a_i$ ，最终其变为 $b_i$ ， $a$ 的前缀和为 $s a$ ， $b$ 的前缀和为 $s b$
如果写过糖果传递，一道与本题类似的题目，不难知道，最终的结果为 $\sum |sa_i-sb_i|$
证明如下：
令 $c_i=a_i-b_i$ 。在位置 $1$ ，我们需要 $c_1|$ 次操作，如果 $c_1<0$ 表示位置 $1$ 向 $2$ 拿了 $c_1|$ 个，反之，表示给了 $c_1$ 个
当到了位置 $2$ ，此时位置 $2$ 的数字应该是 $a_2+a_1-b_1$ ，还应该操作 $a_2+a_1-b_1-b_2$ 来向位置 $3$ 多退少补
于是以此类推
$\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }a_1-b_1\\i=2 \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }a_1-b_1+a_2-b_2\\ \\i=3 \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }a_1-b_1+a_2-b_2+a_3-b_3 \\...$
答案为 $\sum |sa_i-sb_i|$
本题的正确解法为 $D P$
定义 $dp\{i,j,k\}$ 表示在前 $i$ 个数中，前 $i$ 位之和为 $j$ ，第 $i$ 位上的数字为 $k$ ，此时前 $i$ 位数字需要的操作次数
如果第 $i ? 1$ 位数字为 $p$
$dp[i][j][k]=dp[i-1][j-k][p]+abs(sa_i-sb_i)$

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+7;
int f[255][255][255];
int a[255],sum[255];
int main()
{
    memset(f,0x3f,sizeof(f));
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
    if(n==1)
    {
        puts("0");return 0;
    }
    int ans=inf;
    for(int i=0;i<=m;i++) f[1][i][i]=abs(a[1]-i);
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int pre=0;pre<=j;pre++)
            {
                for(int k=0;k<=pre&&k+pre<=j;k++)
                {
                    f[i][j][k]=min(f[i][j][k],f[i-1][j-k][pre]+abs(sum[i]-j));
                    if(i==n&&j==m) ans=min(ans,f[i][j][k]);
                }
            }
        }
    }
    printf("%d\n",ans);

}