头像

妙WA种子_




离线:19小时前



题目描述


算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;

// Tag: 多重背包 记录种类数 
//这个nt写法会超时!
/*
状态表示:

f[i][j] 表示 j 能否由前 i 种物品拼成 

属性:可能性 

状态转移: 
对于最后一个物品 i ,面值为 wi, 数量为 ci

f[i][j] =  f[i-1][j-k*wi] (k<=ci && k*wi<=j) 

然后,在最后一维度,遍历所有的 j ,如果为1,则说明可以组成,cnt++。 

*/

/*
这样写肯定会超时,得考虑其他的状态表示。
状态表示:
f[i,j]表示前i钟硬币能够组成的状态种类数 


属性:数量

状态转移: 

*/

const int N=110, M=1e5+10;

int f[N][M];
int n,m;
int a[M],c[M];

int main()
{
    while(scanf("%d %d",&n,&m),n+m)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);

        for(int i=1;i<=n;i++) scanf("%d",&c[i]);

        memset(f,0,sizeof f);

        for(int i=0;i<=c[1] && i*a[1]<=m;i++) f[1][i*a[1]]=1;
        for(int i=1;i<=n;i++) f[i][0]=1;

        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j] = f[i-1][j];

                if(f[i][j]==0)
                for(int k=1;k<=c[i] && k*a[i]<=j;k++)
                {
                    if(f[i-1][j-k*a[i]]==1)
                    {
                        f[i][j]=1;
                        break;
                    }
                }


            }
        }

        int ans=0;

        for(int i=1;i<=m;i++)
        {
            if(f[n][i]==1) ans++;
        }

        cout<<ans<<endl;

    }


    return 0;
}




算法2

C++ 代码

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

using namespace std;

/*
上一种写法一定会超时的。

1. 每次都要重复赋值, 因为f[i][j]只能赋值0,1,而且一旦赋值为1
之后,就不可能赋值为0,所以,前一种写法的 浪费了很大时间来重复 
给同一最终状态赋值。

2. 对于同一 j 来说,第一种写法需要 再遍历 k 次,看其中是否有 
能够拼成的。这没有利用好条件。
j从小到大遍历,所以说,在i这一唯,不需要每个都判j次,如果上一个
j-v[i]它不能拼成,现在的和以后的都不能拼成。 


*/

const int N = 110, M = 100010;

int n, m;
int f[M], g[M];
int v[N], s[N];

int main()
{
    while (scanf("%d%d", &n, &m), n || m)
    {
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);

        f[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            memset(g, 0, sizeof g);
            for (int j = v[i]; j <= m; j ++ )
                if (!f[j] && f[j - v[i]] && g[j - v[i]] < s[i])
                {
                    g[j] = g[j - v[i]] + 1;
                    f[j] = 1;
                }
        }

        int res = 0;
        for (int i = 1; i <= m; i ++ ) res += f[i];

        printf("%d\n", res);
    }

    return 0;
}

dl的更多写法:
(题解和题解里的评论)
https://www.acwing.com/solution/content/11075/



活动打卡代码 AcWing 281. 硬币

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

using namespace std;

/*
上一种写法一定会超时的。

1. 每次都要重复赋值, 因为f[i][j]只能赋值0,1,而且一旦赋值为1
之后,就不可能赋值为0,所以,前一种写法的 浪费了很大时间来重复 
给同一最终状态赋值。

2. 对于同一 j 来说,第一种写法需要 再遍历 k 次,看其中是否有 
能够拼成的。这没有利用好条件。
j从小到大遍历,所以说,在i这一唯,不需要每个都判j次,如果上一个
j-v[i]它不能拼成,现在的和以后的都不能拼成。 


*/

const int N = 110, M = 100010;

int n, m;
int f[M], g[M];
int v[N], s[N];

int main()
{
    while (scanf("%d%d", &n, &m), n || m)
    {
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);

        f[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            memset(g, 0, sizeof g);
            for (int j = v[i]; j <= m; j ++ )
                if (!f[j] && f[j - v[i]] && g[j - v[i]] < s[i])
                {
                    g[j] = g[j - v[i]] + 1;
                    f[j] = 1;
                }
        }

        int res = 0;
        for (int i = 1; i <= m; i ++ ) res += f[i];

        printf("%d\n", res);
    }

    return 0;
}




C++ 代码

#include<bits/stdc++.h>
using namespace std;

//Tag: 01背包 求具体方案 

/*
状态表示:

f[i,j,k] 所有,从前i个人中选择j个人,且差值为k的所有方案的集合。 

属性:f中保存集合中所有方案的最大值
即方案中p[i]+d[i]的最大值。 

状态计算:
依据是否选择第 i 个人,把 f[i,j,k]集合进行划分。

不选第i个人: f[i-1,j,k]
选择第i个人: f[i-1,j-1,k-(Pi-Di)] + Pi+Di

f[i,j,k] = max(f[i-1,j,k],  f[i-1,j-1,k-(Pi-Di)] + Pi+Di )

注意,k这一维度 为差值, 范围在 -400,+400 之间。 加+400的偏移
因为数组下标恒为正。 

如何求具体方案;
从终点开始逆向判断,看每一种状态是从哪一种状态转移过来的。 

*/

const int N=210,M=810,base = 400;

int n,m;
int p[N],d[N];
int f[N][21][M];
int ans[N]; 

int main()
{
    int T=1;
    while(scanf("%d %d",&n,&m),n||m)
    {
        for(int i=1;i<=n;i++) scanf("%d %d",&p[i],&d[i]);

        memset(f,-0x3f,sizeof f);
        f[0][0][base]=0;    //初始条件从 f(0,0,0) 开始转移,不过要记得偏移量。

        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
                for(int k=0;k<M;k++)
                {
                    f[i][j][k] = f[i-1][j][k];
                    int t = k-(p[i]-d[i]);
                    if(t<0 || t>=M) continue;
                    if(j<1) continue;
                    f[i][j][k] = max(f[i][j][k],f[i-1][j-1][t]+p[i]+d[i]);
                } 


        //判断最优解 是 最终状态集合中的哪一个
        //也就是确定 k 的取值,这里记作 v 
        int v=0;
        while(f[n][m][base-v]<0 && f[n][m][base+v]<0) v++;

        if(f[n][m][base-v]>f[n][m][base+v]) v = base-v;
        else v = base+v; 

        //记录具体方案 
        int cnt=0;
        int i=n,j=m,k=v;
        while(j)
        {
            if(f[i][j][k]==f[i-1][j][k]) i--;
            else
            {
                ans[cnt++] = i;
                k -= (p[i]-d[i]);
                i--,j--;
            }
        }

        //根据题意输出具体方案中的 p 和 d 的总和 
        int sp=0,sd=0;
        for(int i=0;i<cnt;i++)
        {
            sp+=p[ans[i]];
            sd+=d[ans[i]];
        }

        printf("Jury #%d\n", T ++ );
        printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd);

        //需要排序后输出答案 
        sort(ans, ans + cnt);
        for (int i = 0; i < cnt; i ++ ) printf(" %d", ans[i]);
        puts("\n");
    }


    return 0;
}





活动打卡代码 AcWing 280. 陪审团

#include<bits/stdc++.h>
using namespace std;

//Tag: 01背包 求具体方案 

/*
状态表示:

f[i,j,k] 所有,从前i个人中选择j个人,且差值为k的所有方案的集合。 

属性:f中保存集合中所有方案的最大值
即方案中p[i]+d[i]的最大值。 

状态计算:
依据是否选择第 i 个人,把 f[i,j,k]集合进行划分。

不选第i个人: f[i-1,j,k]
选择第i个人: f[i-1,j-1,k-|Pi-Di|] + |Pi-Di|

f[i,j,k] = max(f[i-1,j,k],  f[i-1,j-1,k-(Pi-Di)] + Pi-Di )

注意,k这一维度 为差值, 范围在 -400,+400 之间。 加+400的偏移
因为数组下标恒为正。 

如何求具体方案;
从终点开始逆向判断,看每一种状态是从哪一种状态转移过来的。 

*/

const int N=210,M=810,base = 400;

int n,m;
int p[N],d[N];
int f[N][21][M];
int ans[N]; 

int main()
{
    int T=1;
    while(scanf("%d %d",&n,&m),n||m)
    {
        for(int i=1;i<=n;i++) scanf("%d %d",&p[i],&d[i]);

        memset(f,-0x3f,sizeof f);
        f[0][0][base]=0;    //初始条件从 f(0,0,0) 开始转移,不过要记得偏移量。

        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++)
                for(int k=0;k<M;k++)
                {
                    f[i][j][k] = f[i-1][j][k];
                    int t = k-(p[i]-d[i]);
                    if(t<0 || t>=M) continue;
                    if(j<1) continue;
                    f[i][j][k] = max(f[i][j][k],f[i-1][j-1][t]+p[i]+d[i]);
                } 


        //判断最优解 是 最终状态集合中的哪一个
        //也就是确定 k 的取值,这里记作 v 
        int v=0;
        while(f[n][m][base-v]<0 && f[n][m][base+v]<0) v++;

        if(f[n][m][base-v]>f[n][m][base+v]) v = base-v;
        else v = base+v; 

        //记录具体方案 
        int cnt=0;
        int i=n,j=m,k=v;
        while(j)
        {
            if(f[i][j][k]==f[i-1][j][k]) i--;
            else
            {
                ans[cnt++] = i;
                k -= (p[i]-d[i]);
                i--,j--;
            }
        }

        //根据题意输出具体方案中的 p 和 d 的总和 
        int sp=0,sd=0;
        for(int i=0;i<cnt;i++)
        {
            sp+=p[ans[i]];
            sd+=d[ans[i]];
        }

        printf("Jury #%d\n", T ++ );
        printf("Best jury has value %d for prosecution and value %d for defence:\n", sp, sd);

        //需要排序后输出答案 
        sort(ans, ans + cnt);
        for (int i = 0; i < cnt; i ++ ) printf(" %d", ans[i]);
        puts("\n");
    }


    return 0;
}






C++ 代码

#include<bits/stdc++.h>
using namespace std;

//Tag: 完全背包记录方案数

/*
状态表示:
f[i][j] 表示前 i 个物品, 组合成权值为 j 的种类数 

属性:种类数
要求方案划分不重不漏。

状态计算:
题目要求不考虑顺序,也就是 1 + 2 和 2 + 1 是同一种类型。
而且 3 = 3 不算一种方案。 ACwing和蓝书有些不同。

f[i][j] = f[i-1][j] + f[i-1][j-i]

注意:
1. 和一般的多重背包状态更新不一样, 
这道题不能用 k 次循环更新,否则会计算重复。
2. 更新的过程中 j 从 i 开始循环,在 i 之前没有意义。 
3. 2147483648 爆int 用LL来存。 


*/ 

typedef long long LL; 

const int N=4010;
const LL mod = 2147483648;

int n;
LL f[N];

int main()
{
    scanf("%d",&n);

    f[0]=1;

    for(int i=1;i<n;i++)
    {   //因为 n = n 不算一种方案, i不能枚举到 n 
        for(int j=i;j<=n;j++)
        {
            f[j] = (f[j]+f[j-i])%mod;
        }
    }

    printf("%d",f[n]);

    return 0;
}




活动打卡代码 AcWing 279. 自然数拆分

#include<bits/stdc++.h>
using namespace std;

//Tag: 完全背包记录方案数

/*
状态表示:
f[i][j] 表示前 i 个物品, 组合成权值为 j 的种类数 

属性:种类数
要求方案划分不重不漏。

状态计算:
题目要求不考虑顺序,也就是 1 + 2 和 2 + 1 是同一种类型。
而且 3 = 3 不算一种方案。 ACwing和蓝书有些不同。

f[i][j] = f[i-1][j] + f[i-1][j-i]

注意:
1. 和一般的多重背包状态更新不一样, 
这道题不能用 k 次循环更新,否则会计算重复。
2. 更新的过程中 j 从 i 开始循环,在 i 之前没有意义。 
3. 2147483648 爆int 用LL来存。 


*/ 

typedef long long LL; 

const int N=4010;
const LL mod = 2147483648;

int n;
LL f[N];

int main()
{
    scanf("%d",&n);

    f[0]=1;

    for(int i=1;i<n;i++)
    {   //因为 n = n 不算一种方案, i不能枚举到 n 
        for(int j=i;j<=n;j++)
        {
            f[j] = (f[j]+f[j-i])%mod;
        }
    }

    printf("%d",f[n]);

    return 0;
}



活动打卡代码 AcWing 277. 饼干

#include<bits/stdc++.h>
using namespace std;

//Tag: 线性DP 记录具体方案 

/*
所有DP问题都可以从集合角度来解释。一般的DP问题都是在有限集合
内求最值或求个数,极个别的DP问题会在无限集合内求最值,此时
先将无限集想办法缩小到有限集即可,
如: 分级  https://www.acwing.com/problem/content/275/

根据排序不等式,我们发现在本问题所包括的分配方案的全集中,
最优解一定在如下的子集中:

将所有小朋友按愤怒值g[i]从大小到小排序,
排名靠前的小朋友分配的饼干要更多一些。

状态表示:
f[i][j] 表示: 
所有将j个饼干分配给前i个小朋友,且分配的饼干数单调下降的分配方案。

属性:最小值 

状态计算:
集合划分依据: 最后有几个小朋友分配 1 个饼干。 


最后求方案数只需倒推一遍,找出每个状态是由哪个状态计算得到的即可。

*/ 

typedef pair<int,int> PII; 

const int N = 40, M = 5010;

int n,m;
PII g[N];
int s[N];
int f[N][M];
int ans[N];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&g[i].first);
        g[i].second = i;
    }
    sort(g+1,g+n+1);
    reverse(g+1,g+n+1);

    //前缀和优化 
    for(int i=1;i<=n;i++) s[i] = s[i-1] + g[i].first;

    memset(f,0x3f,sizeof f);
    f[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j>=i) f[i][j] = f[i][j-i];
            for(int k=1;k<=i && k<=j;k++)
                f[i][j] = min(f[i][j], f[i-k][j-k]+(s[i]-s[i-k])*(i-k));
        }
    }

    cout<<f[n][m]<<endl;

    int i=n,j=m,h=0;    //h表示当前之前的孩子,因为所有都分一个而得到的糖果数量 
    while(i && j)
    {
        //如果结果相同,任意输出一种方案即可,所以不用考虑相同情况下选择哪一种 
        if(j>=i && f[i][j] == f[i][j-i]) j-=i, h++;
        else
        {
            for(int k=1;k<=i && k<=j;k++)
                if(f[i][j] == f[i-k][j-k]+(s[i]-s[i-k])*(i-k))
                {
                    for(int u=i;u>i-k;u--) 
                        ans[g[u].second] = 1+h;

                    i-=k, j-=k;
                    break;
                }

        }
    }

    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    cout<<endl;

    return 0;
}




活动打卡代码 AcWing 276. I-区域

#include<bits/stdc++.h>
using namespace std;

//Tag: 线性DP 记录具体方案 

/*

状态表示:
 f[i,j,L,R,x,y] 
所有选完前i行,且一共选择了j个格子,且第i行选择的左边界是L,
第i行选择的右边界是R,且左边界递增、递减状态时x,右边界的递增、递减状态
是y的连通块的集合。 

属性:最大值 

状态计算:

使用状态机模型:
对于左边界来说,递减状态可以由起始状态、递减状态转移过来,不能右递增转移过来(凸连通块) 
递增状态可以由递减状态、本身状态转移过来。 
在任意状态都可以转移到结束状态。 

对于左边界:
f[i,j,L,R,1,0] = f[i-1,j-(R-L+1),1,0] 。。。。。。
类似的,左边界扩张,右边界扩张;左边界扩张,右边界收缩;左收缩,右扩张;
左收缩,右收缩,都根据状态机的定义进行转移。 

记录具体方案:
和记录最短路的问题类似,记录每一种状态是由什么状态转移过来的。
并记录下来。 

*/ 

const int N=16;

int n,m,k;
int w[N][N];
int f[N][N*N][N][N][2][2];
//1为纵坐标减少,0为纵坐标增加 

struct State{
    int i,j,l,r,x,y;
}g[N][N*N][N][N][2][2];

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>w[i][j];

    memset(f,-0x3f,sizeof f);

    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
            for(int l=1;l<=m;l++)
                for(int r=l;r<=m;r++)
                {
                    if(j<r-l+1) continue;   //如果 j 和l,r之间的状态不符合定义,就直接continue

                    //左扩张,右扩张 
                    {
                        auto &vf = f[i][j][l][r][1][0];
                        auto &vg = g[i][j][l][r][1][0];

                        if(j == r-l+1) vf = 0;
                        //p,q为上一行的左右坐标;l,r为本行的左右坐标 
                        for(int  p=l;p<=r;p++)
                            for(int q=l;q<=r;q++)
                            {
                                int val = f[i-1][j-(r-l+1)][p][q][1][0];
                                if(vf < val)
                                {
                                    vf = val;
                                    vg = {i-1,j-(r-l+1),p,q,1,0};
                                }
                            }
                        for(int u=l;u<=r;u++) vf += w[i][u];
                    }

                    //左扩张,右收缩 
                    {
                        auto &vf = f[i][j][l][r][1][1];
                        auto &vg = g[i][j][l][r][1][1];

                        for(int p=l;p<=r;p++)
                            for(int q=r;q<=m;q++)
                                for(int y=0;y<=1;y++)   //收缩状态可以由扩张状态转移而来 
                                {
                                    int val = f[i-1][j-(r-l+1)][p][q][1][y];
                                    if(vf<val)
                                    {
                                        vf = val;
                                        vg = {i-1,j-(r-l+1),p,q,1,y};
                                    }
                                }
                        for(int u=l;u<=r;u++) vf += w[i][u];
                    }

                    //左收缩,右扩张 
                    {
                        auto &vf = f[i][j][l][r][0][0];
                        auto &vg = g[i][j][l][r][0][0];

                        for(int p=1;p<=l;p++)
                            for(int q=l;q<=r;q++)
                                for(int x=0;x<=1;x++)
                                {
                                    int val = f[i-1][j-(r-l+1)][p][q][x][0];
                                    if(vf < val)
                                    {
                                        vf = val;
                                        vg = {i-1,j-(r-l+1),p,q,x,0};
                                    }
                                }
                        for(int u=l;u<=r;u++) vf += w[i][u];
                    }

                    //左收缩,右收缩 
                    {
                        auto &vf = f[i][j][l][r][0][1];
                        auto &vg = g[i][j][l][r][0][1];
                        for(int p=1;p<=l;p++)
                            for(int q=r;q<=m;q++)
                                for(int x=0;x<=1;x++)
                                    for(int y=0;y<=1;y++)
                                    {
                                        int val = f[i-1][j-(r-l+1)][p][q][x][y];
                                        if(vf < val)
                                        {
                                            vf = val;
                                            vg = {i-1,j-(r-l+1),p,q,x,y};
                                        }
                                    }
                        for(int u=l;u<=r;u++) vf += w[i][u];
                    }

                }

    int res=0;
    State state;

    for(int i=1;i<=n;i++)
    {
        for(int l=1;l<=m;l++)
        {
            for(int r=1;r<=m;r++)
            {
                for(int x=0;x<=1;x++)
                {
                    for(int y=0;y<=1;y++)
                    {
                        int val = f[i][k][l][r][x][y];
                        if(res < val)
                        {
                            res = val;
                            state = {i,k,l,r,x,y};
                        }
                    }
                }
            }
        }
    }

    printf("Oil : %d\n",res);

    while(state.j)
    {
        for(int i = state.l;i <= state.r ;i++) printf("%d %d\n",state.i,i);
        state = g[state.i][state.j][state.l][state.r][state.x][state.y];
    }

    return 0;
}





活动打卡代码 AcWing 274. 移动服务

#include<bits/stdc++.h>
using namespace std;

//Tag: 线性DP 状态机模型

/*

状态表示:

错误想法: dp[i][j][k] 表示三个人的位置分别在 i,j,k ,但是,还需要
记录当前处理的请求数,才能完整地表示状态,dp[i][j][k][l] ,
但是 200*200*200*4*1000 ≈ 3200 MB 必超。 

正确想法: 肯定要优化掉一维空间。 由于是移动到请求位置,然后再处理请求
所以: 
f[i][x][y]表示已经处理完前i个请求,且三个服务员分别在p[i], x, y的所有方案的集合;
f[i][x][y]的值是集合中所有方案的花费的最小值;

属性: 最小值;所以在划分进行状态计算的侍候可以重叠,不能遗漏。

初始化: 求最小值 ,应该初始化为最大值 

状态计算:
这里状态之间的拓扑关系比较特殊,f[i][x][y]所依赖的状态枚举起来不太方便,但f[i][x][y]被依赖的很容易枚举,只有3类:

位于p[i]的服务员出发前往p[i + 1],此时状态变成f[i + 1][x][y] = f[i][x][y] + w[p[i]][p[i + 1]];
位于x的服务员出发前往p[i + 1],此时状态变成f[i + 1][p[i]][y] = f[i][x][y] + w[x][p[i + 1]];
位于y的服务员出发前往p[i + 1],此时状态变成f[i + 1][x][p[i]] = f[i][x][y] + w[y][p[i + 1]];
最终答案从f[m][1...n][1...n]取最小值即可。

链接:https://www.acwing.com/solution/content/4957/
*/ 

const int N = 210, M=1010, INF = 0x3f3f3f3f;

int n,m;
int w[N][N];
int f[M][N][N];
int p[M];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&w[i][j]);
    for(int i=1;i<=m;i++) scanf("%d",&p[i]);

    p[0]=3;
    memset(f,0x3f,sizeof f);
    f[0][1][2]=0;
    for(int i=0;i<m;i++)
        for(int x=1;x<=n;x++)
            for(int y=1;y<=n;y++)
            {
                int z = p[i], v = f[i][x][y];
                if(x==y || x==z || y==z) continue;
                int u = p[i+1];
                f[i+1][x][y] = min(v+w[z][u],f[i+1][x][y]);
                f[i+1][z][y] = min(v+w[x][u],f[i+1][z][y]); 
                f[i+1][x][z] = min(v+w[y][u],f[i+1][x][z]);
            }

    int  res = INF;
    for(int x=1;x<=n;x++)
        for(int y=1;y<=n;y++)
        {
            int z = p[m];
            if(x==y || x==z || y==z) continue;
            res = min(res,f[m][x][y]);
        }

    printf("%d\n",res);

    return 0;
}






活动打卡代码 AcWing 273. 分级

#include<bits/stdc++.h>
using namespace std;

//Tag:线性DP,前缀和思想优化

//像这种线性DP,二维去做的话,一般能想到 f(i,j) 表示
//维护以 i,j为结尾的 状态集合。 
//如果发现这样写 状态计算表示不出来, 
//就可以想 是不是 i表示一段 ,j表示末尾,并且 用序列中到数第二个来更新最后一个。 

/*

首先需要证明引理:

存在这么一组最优解,使得构造的B数组中的每个数都在A中出现过。 

可以用归纳法,这个不要看ACwing,看蓝书比较好理解。

状态表示:
f[i][j] 代表所有给A[1] ~ A[i]分配好了值
且 最后一个B[i] = A'[j]的方案的集合;

属性:最小值 

状态计算:
依据倒数第二个数分配的是哪个A'[i]将f[i][j]所代表的集合划分成j个不重不漏的子集:

倒数第二个数选取的是A'[1]的所有方案的结合,最小值是 f[i - 1][1] + abs(A[i] - A'[j]);
倒数第二个数选取的是A'[2]的所有方案的结合,最小值是 f[i - 1][2] + abs(A[i] - A'[j]);
倒数第二个数选取的是A'[j]的所有方案的结合,最小值是 f[i - 1][j] + abs(A[i] - A'[j]);

f[i][j]在所有子集的最小值中取min即可。

*/ 

const int N=2010, INF = 0x3f3f3f3f;

int n;
int a[N],b[N];
int f[N][N];

int work()
{
    for(int i=1;i<=n;i++) b[i] = a[i];
    sort(b+1,b+1+n);

    for(int i=1;i<=n;i++)
    {
        int minv = INF;
        for(int j=1;j<=n;j++)
        {
            //这里对minv的处理在前面,因为f[i][j]也可以由f[i-1][j]转移过来. 
            minv = min(minv,f[i-1][j]);
            f[i][j] = minv + abs(a[i]-b[j]);
        }
    }

    int res = INF;
    for(int i=1;i<=n;i++) res = min(res,f[n][i]);

    return res;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    int res = work();
    reverse(a+1,a+1+n);
    res = min(res,work());

    printf("%d\n",res);

    return 0;   
}