CF--787--G

感觉是很经典的现实问题，原来是使用dp进行处理的。对每一个状态都定义一下子就好了

思路

可以逆序一下，这样子就变成递增，将问题进行合理转换
关键是状态转换的代价如何就算，这个需要讲究，其实是前缀和的差值
f(i,j,k)前面i个，选了j个，最后一个是k的最小代价
大致就是：确定dp转移的方程，然后确定转移的代价

代码

#include <bits/stdc++.h>
using namespace std;
const int M=255;
const int inf=0x3f3f3f3f;

int f[M][M][M],sum[M];

int main() {
    int n,m;cin>>n>>m;
    for(int i=n;i;i--)cin>>sum[i];
    for(int i=1;i<=n;i++)sum[i]=sum[i]+sum[i-1];
    memset(f,0x3f,sizeof(f));
    f[0][0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++) {//这里枚举i-1的状态，因为是要从i-1转移过来
            int mn=inf;
            for(int k=0;j+k<=m;k++) {//i-1选多少个，i的最后一个选多少个，那么前i个选了多少也就是确定的
                mn=min(mn,f[i-1][j][k]);//比他小的人中找一个小的就可以了
                f[i][j+k][k]=mn+abs(sum[i]-j-k);
                //多了就给后面，少了就找后面要，这就是dp转移的代价
                
                //int mn=inf;
                //for(int l=0;l<=k;l++)
                //    mn=min(mn,f[i-1][j][l]);
                //f[i][j+k][k]=mn+abs(sum[i]-j-k);
                //每次在前面找一个最小的，其实这一个维度是可以省去的
            }
        }
    int ans=inf;
    for(int i=1;i<=m;i++)ans=min(ans,f[n][m][i]);
    cout<<ans;
    return 0;
}