acm之旅--保研练习系列-程序员宅基地

技术标签： ACM

文章目录

A - Max Sum Plus Plus

题目链接：A - Max Sum Plus Plus
参考博文：Max Sum Plus Plus （动态规划+m子段和的最大值）

思路：
- 状态构造：dp[i][j]表示前j个数分成i组（第j个数字一定在组内）的最大和。
- max(dp[m][j])
- 动态转移方程：dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j]) (0<k<j)。
  dp[i][j-1]+a[j]表示的是前j-1分成i组，第j个必须放在前一组里面。
  max( dp[i-1][k] ) + a[j] )表示的前（0<k<j）分成i-1组，第j个单独分成一组。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 1000005;
int dp[MAX], a[MAX];
int Max[MAX];

int main()
{
    
    int n, m;
    while(cin >> m >> n)
    {
    
        for(int i=1; i<=n; i++)
        cin >> a[i];
        memset(dp, 0, sizeof(dp));
        memset(Max, 0, sizeof(Max));
        int mmax;//表示当前最大值
        for(int i=1; i<=m; i++)
        {
    
            mmax = -1<<29;
            for(int j=i; j<=n; j++)
            {
    
                dp[j] = max(dp[j-1]+a[j], Max[j-1]+a[j]);
                Max[j-1] = mmax;//更新后用于下一个i循环，代表max(dp[i-1][k])
                mmax = max(mmax, dp[j]);//一直保持在前
            }
        }
        cout << mmax << endl;
    }
    return 0;
}

B - Ignatius and the Princess IV

题目链接：B - Ignatius and the Princess IV

思路：水题。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

typedef long long LL;
map<LL, LL> m;
int main()
{
    
    int N;
    LL a, ans;
    while(scanf("%d", &N)!=EOF)
    {
    
        m.clear();
        int res = (N+1)/2;
        for(int i=0; i<N; i++)
        {
    
            scanf("%lld", &a);
            m[a]++;
            if(m[a]==res) ans = a;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C - Monkey and Banana

题目链接：C - Monkey and Banana

思路：这是《算法竞赛入门（第二版）》中的一道题，具体见中的437题。难点在与状态的构造，使用维这一个变量，简化的方法。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int a[50][5], dp[50][5], n;

void Init(int n)
{
    
    for(int i=0; i<=n; i++)
    {
    
        for(int j=0; j<3; j++)
            dp[i][j] = 0;
    }
}
bool check(int i, int j, int k, int t)
{
    
    vector<int> m1, m2;
    for(int h=0; h<3; h++)
    {
    
        if(h!=j) m1.push_back(a[i][h]);
        if(h!=t) m2.push_back(a[k][h]);
    }
    if(m1[0]<=m2[0] || m1[1]<=m2[1]) return 0;
    else                             return 1;
}
int DP(int i, int j)
{
    
    int &ans = dp[i][j];
    if(ans>0) return ans;
    ans = a[i][j];
    for(int k=1; k<=n; k++)
    {
    
        for(int t = 0; t<3; t++)
        {
    
            if(check(i, j, k, t))
            {
    
                ans = max(ans, DP(k, t)+a[i][j]);
            }
        }
    }
    return ans;
}
int main()
{
    
    int kase = 1;
    while(scanf("%d", &n)!=EOF && n)
    {
    
        for(int i=1; i<=n; i++)
        {
    
            scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
            sort(a[i], a[i]+3);
        }
        Init(n);
        int Max = 0;
        for(int i=1; i<=n; i++)
        {
    
            for(int j=0; j<3; j++)
            {
    
                Max = max(Max, DP(i, j));
            }
        }
        printf("Case %d: maximum height = %d\n", kase++, Max);
    }
    return 0;
}

D - Doing Homework

题目链接：D - Doing Homework

E - Super Jumping! Jumping! Jumping!

题目链接：E - Super Jumping! Jumping! Jumping!

思路：LIS的简单变体，由求最长递增子序列的长度变为求最长递增子序列的和，套用即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    
    int N, a[1005], dp[10005];
    while(cin >> N && N)
    {
    
        for(int i=1; i<=N; i++)
            cin >> a[i];
        memset(dp, 0, sizeof(dp));
        a[0] = -1<<29;
        int ans = 0;
        for(int i=1; i<=N; i++)
        {
    
            for(int j=0; j<i; j++)
            {
    
                if(a[j]<a[i])
                    dp[i] = max(dp[i], dp[j]+a[i]);
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

F - Piggy-Bank

题目链接：F - Piggy-Bank

思路：一个完全背包的模板题，注意数组不要开小了。。。。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int INF = 1<<29;
struct Node
{
    
    int p, w;
};
Node coin[1000];
int dp[10005];//注意数组大小，开小了可能TLE

int main()
{
    
    int T, E, F, N, n;
    scanf("%d", &T);
    while(T--)
    {
    
        scanf("%d%d", &E, &F);
        N = F-E;
        scanf("%d", &n);
        fill(dp, dp+N+1, INF);
        dp[0] = 0;
        for(int i=1; i<=n; i++)
        {
    
            scanf("%d%d", &coin[i].p, &coin[i].w);
            for(int j=coin[i].w; j<=N; j++)
            {
    
                dp[j] = min(dp[j], dp[j-coin[i].w]+coin[i].p);
            }
        }
        if(dp[N]==INF)
            printf("This is impossible.\n");
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[N]);
     }
    return 0;
}

G - 免费馅饼

题目链接：G - 免费馅饼
参考博文： G. 免费馅饼

思路：动态规划题目。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int a[100005][11], dp[100005][11];//a[i][j]为第i秒的j位置掉下的馅饼数量,dp[i][j]表示第i秒在j位置总共接了多少个馅饼
int dx[5] = {
    -1, 0, 1};
int DP(int i, int j)
{
    
    int &ans = dp[i][j];
    if(ans>0 || i==1) return ans;
    int st = 0, ed = 3;
    if(j==0) st = 1;
    else if(j==10) ed = 2;
    for(int k=st; k<ed; k++)
    {
    
        ans = max(ans, DP(i-1, j+dx[k])+a[i][j]);
    }
    return ans;
}
int main()
{
    
    int n, b, c;
    while(scanf("%d", &n)!=EOF && n)
    {
    
        int T = 0;
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
    
            scanf("%d%d", &b, &c);
            a[c][b]++;
            if(T<c) T = c;
        }
        dp[1][4] = a[1][4], dp[1][5] = a[1][5], dp[1][6] = a[1][6];
        int Max = 0;
        for(int j=0; j<=10; j++)
        {
    
            Max = max(Max, DP(T, j));
        }
        printf("%d\n", Max);
    }
    return 0;
}

H - Tickets

题目链接：H - Tickets

思路：
- 状态构造：dp[i]表示前i个人所需取票的时间。
- 终态：dp[K]，K为总人数。
- 状态转移方程：dp[i] = min(dp[i-1]+a[i], dp[i-2]+b[i-1])，a[i]表示第i个人取票的时间，b[i-1]表示第i-1和第i个人一起取票的时间。
- 初始化：dp[0] = 0.
  我使用了记忆化搜索。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int MAX = 5000;
int a[MAX], b[MAX], dp[MAX];
int DP(int i)
{
    
    if(i<0) return 0;//注意i<0的情况
    int &ans = dp[i];
    if(ans!=-1) return ans;
    if(i>1) ans = min(DP(i-1)+a[i], DP(i-2)+b[i-1]);
    else    ans = a[i];//i==1时，为a[1]
    return ans;
}
int main()
{
    
    int N, K;
    scanf("%d", &N);
    while(N--)
    {
    
        vector<int> ans;
        scanf("%d", &K);
        for(int i=1; i<=K; i++)
        {
    
            scanf("%d", &a[i]);
        }
        for(int i=1; i<K; i++)
        {
    
            scanf("%d", &b[i]);
        }
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        int t = DP(K);
        //换算时间
        int h = t/3600+8;
        t = t%3600;
        int m = t/60;
        t = t%60;
        printf("%02d:%02d:%02d ", h, m, t);
        if(h>=12) printf("pm");//中午12点是pm，晚上12点是am
        else      printf("am");
        printf("\n");
    }
    return 0;
}

I - 最少拦截系统

题目链接：I - 最少拦截系统

思路：类似于最长非增子序列，但是需要求非增子序列的最少个数，因此可以使用一个数组d来存储每一个非增子序列的末尾元素，如果当前元素小于等于其中的元素，则更新最接近它的元素，如果均小于它，则将该元素添加到数组中，最后数组的大小即为所求。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int MAX = 500000;
int a[MAX], dp[MAX];
vector<int> d;//记录每一个非增子序列的末尾元素,更新时一定是从小到大排好序
int main()
{
    
    int n;
    while(scanf("%d", &n)!=EOF)
    {
    
        d.clear();
        for(int i=1; i<=n; i++)
            scanf("%d", &a[i]);
        fill(dp, dp+n+1, 1);
        d.push_back(a[1]);
        for(int i=2; i<=n; i++)
        {
    
            int j;
            for(j=0; j<d.size(); j++)
            {
    
                if(d[j]>=a[i])//表明a[i]可以加入d[j]结尾的序列中，因此更新末尾元素
                {
    
                    d[j] = a[i];
                    break;
                }
            }
            if(j==d.size()) dp[i] = dp[i-1]+1, d.push_back(a[i]);//表明没有更新
            else            dp[i] = dp[i-1];
        }
        printf("%d\n", d.size());
    }
    return 0;
}

J - FatMouse’s Speed

题目链接：J - FatMouse’s Speed

思路：保证按重量递增但是同时速度递减，则可以先按重量从小到大排序，然后就是对于速度的最大递减子序列，但是需要记录序列，可以使用pre数组记录路径。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

struct Node
{
    
    int w, s, id;
    bool operator < (const Node &A) const
    {
    
        if(w==A.w) return s>A.s;
        else       return w<A.w;
    }
};
Node M[2000];
int pre[10005], dp[2000];//dp表示前i个的子序列长度

int main()
{
    
    int cnt = 1;
    while(scanf("%d%d", &M[cnt].w, &M[cnt].s)!=EOF)
    {
    
        M[cnt].id = cnt;
        cnt++;
    }
    sort(M+1, M+cnt);
    fill(dp, dp+cnt+1, 1);
    memset(pre, 0, sizeof(pre));
    for(int i=1; i<cnt; i++)
    {
    
        for(int j=1; j<i; j++)
        {
    
            if(M[j].w<M[i].w && M[j].s>M[i].s)//严格
            {
    
                if(dp[i]<dp[j]+1)
                {
    
                    dp[i] = dp[j]+1;
                    pre[i] = j;
                }
            }
        }
    }
    int Max = 0, idx;
    for(int i=1; i<cnt; i++)
    {
    
        if(Max<dp[i])
        {
    
            Max = dp[i];
            idx = i;//找出末尾下标
        }
    }
    vector<int> ans;
    ans.push_back(M[idx].id);//存储原始编号
    while(pre[idx])
    {
    
        idx = pre[idx];//反向寻找路径
        ans.push_back(M[idx].id);
    }
    printf("%d\n", Max);
    for(int i=ans.size()-1; i>=0; i--)
        printf("%d\n", ans[i]);
    return 0;
}

K - Jury Compromise

题目链接：K - Jury Compromise

思路：

L - Common Subsequence

题目链接：L - Common Subsequence

思路：裸的LCS。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 1000;
int dp[MAX][MAX];
int main()
{
    
    string s1, s2;
    while(cin >> s1 >> s2)
    {
    
        int n = s1.size(), m = s2.size();
        s1 = " "+s1, s2 = " "+s2;
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
    
            for(int j=1; j<=m; j++)
            {
    
                if(s1[i]==s2[j])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        printf("%d\n", dp[n][m]);
    }
    return 0;
}

M - Help Jimmy

题目链接：M - Help Jimmy
参考博文：M - Help Jimmy DP

思路：好题。首先垂直高度一定为Y，不需要考虑，而水平方向需要考虑向左还是向右。
首先将板子按高度从小到大排序，且起始点为高度为Y，长度为0的板子，则起始点一定是最后一个板子。
- 状态构造：dp[i][0]表示在第i个板子上向左走（到地面）的水平时间，dp[i][1]表示在第i个板子上向右走（到地面）的水平时间。
- 终态：dp[n][0]，表示起始点的水平时间。
- 状态转移方程：
  - $d p [i] [0] = m i n (d p [l p] [0] + a [i] . l - a [l p] . l, d p [l p] [1] + a [l p] . r - a [i] . l)$ ;lp表示从第i个板子左边掉落可以到达的板子的下标，a[i].l表示第i个板子的左边缘的水平坐标，a[i].r表示第i个板子的右边缘的水平坐标。
  - $d p [i] [1] = m i n (d p [r p] [0] + a [i] . r - a [r p] . l, d p [r p] [1] + a [r p] . r - a [i] . r)$ ;
- dp[][] = INF
  需要考虑高度是否可以落下，如果不可以则为INF。具体见代码

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1<<29;
const int MAX = 1005;

struct Node
{
    
    int l, r, h;
}a[MAX];
int dp[MAX][2];
bool cmp(Node a, Node b)
{
    
    return a.h<b.h;
}
void Init(int n)
{
    
    for(int i=0; i<=n+1; i++)
    {
    
        for(int j=0; j<2; j++)
            dp[i][j] = INF;
    }
}
int main()
{
    
    int t, n, x, y, d;
    scanf("%d", &t);
    while(t--)
    {
    
        scanf("%d%d%d%d", &n, &x, &y, &d);
        Init(n);
        for(int i=0; i<n; i++)
        {
    
            scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].h);
        }
        a[n].l = a[n].r = x;
        a[n].h = y;
        sort(a, a+n, cmp);//按高度从小到大
        for(int i=0; i<=n; i++)
        {
    
            int lp = -1, rp = -1;//分别为左边和右边板子的编号
            for(int j=i-1; j>=0; j--)//从高度比i低的板子中选择左右板子
            {
    
                if(lp==-1 && a[j].l<=a[i].l && a[j].r>=a[i].l)
                {
    
                    lp = j;
                }
                if(rp==-1 && a[j].r>=a[i].r && a[j].l<=a[i].r)
                {
    
                    rp = j;
                }
            }
            if(lp==-1)//当不存在左边的板子
            {
    
                if(a[i].h<=d) dp[i][0] = 0;//可以直接落到地上
                else          dp[i][0] = INF;//这边不可以落下
            }
            if(rp==-1)
            {
    
                if(a[i].h<=d) dp[i][1] = 0;
                else          dp[i][1] = INF;
            }
            if(lp!=-1 && a[i].h-a[lp].h<=d)//左边的板子可以落下
                dp[i][0] = min(dp[lp][0]+a[i].l-a[lp].l, dp[lp][1]+a[lp].r-a[i].l);
            if(rp!=-1 && a[i].h-a[rp].h<=d)
                dp[i][1] = min(dp[rp][0]+a[i].r-a[rp].l, dp[rp][1]+a[rp].r-a[i].r);
        }
        printf("%d\n", dp[n][0]+y);
    }
    return 0;
}

N - Longest Ordered Subsequence

题目链接：N - Longest Ordered Subsequence

思路：裸的LIS。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[10005], dp[10005];

int main()
{
    
    int N;
    scanf("%d", &N);
    fill(dp, dp+N+1, 1);
    int ans = 0;
    for(int i=1; i<=N; i++)
    {
    
        scanf("%d", &a[i]);
        for(int j=1; j<i; j++)
        {
    
            if(a[j]<a[i])
                dp[i] = max(dp[i], dp[j]+1);
        }
        if(ans<dp[i]) ans = dp[i];
    }
    printf("%d\n", ans);
    return 0;
}

O - Treats for the Cows

题目链接：O - Treats for the Cows
＊思路：一开始看了样例以为是贪心，但是有反例。实则是区间DP。区间DP一般循环时外层都是区间长度。
* 状态构造：dp[i][j]表示序列的第i个到第j个的最大价值。
* 终态：dp[1][N]。
* 状态转移方程： $d p [i] [j] = m a x (d p [i + 1] [j] + a [i] * (N - (j - i)), d p [i] [j - 1] + a [j] * (N - (j - i)))$ ，表示取首部和取尾部的最大值。
* 初始化：dp[i][i] = a[i]*N。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

typedef long long LL;
const int MAX = 2005;
LL a[MAX], dp[MAX][MAX];

int main()
{
    
    int N;
    scanf("%d", &N);
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=N; i++)
    {
    
        scanf("%d", &a[i]);
        dp[i][i] = a[i]*N;
    }
    for(int len = 2; len<=N; len++)
    {
    
        for(int i=1; i<=N; i++)
        {
    
            int j=i+len-1;
            if(j>N) break;
            dp[i][j] = max(dp[i+1][j]+a[i]*(N-(j-i)), dp[i][j-1]+a[j]*(N-(j-i)));
        }
    }
    printf("%lld\n", dp[1][N]);
    return 0;
}

P - FatMouse and Cheese

题目链接：P - FatMouse and Cheese

思路：注意看题意，是只能水平跑或垂直跑。类似于滑雪问题，只不过范围扩大了，依然可以使用记忆化搜索。dp[x][y]表示在(x,y)处可以吃到的最多的奶酪。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n, k;
int G[105][105];
int dp[105][105];
int dx[5] = {
    0, 0, 1, -1};
int dy[5] = {
    1, -1, 0, 0};

int DP(int x, int y)
{
    
    int &ans = dp[x][y];
    if(ans!=-1) return ans;
    ans = G[x][y];
    for(int i=1; i<=k; i++)//步数
    {
    
        for(int j=0; j<=4; j++)//四个方向
        {
    
            int x1 = x+dx[j]*i, y1 = y+dy[j]*i;
            if(x1<0 || x1>=n || y1<0 || y1>=n || G[x1][y1]<=G[x][y]) continue;
            ans = max(ans, DP(x1, y1)+G[x][y]);//转移方程
        }
    }
    return ans;
}
int main()
{
    
    while(scanf("%d%d", &n, &k)!=EOF && n!=-1)
    {
    
        for(int i=0; i<n; i++)
        {
    
            for(int j=0; j<n; j++)
            {
    
                scanf("%d", &G[i][j]);
            }
        }
        memset(dp, -1, sizeof(dp));
        printf("%d\n", DP(0, 0));
    }
    return 0;
}

Q - Phalanx

题目链接：Q - Phalanx
参考博文：hdu 2859 （二维dp）

思路：这道题的状态定义和转移方程构造比较巧妙，值得思考。
- 状态构造：dp[i][j]表示以(i,j)为左下角的对称矩阵的边长。
- 终态：max(dp[i][j])
- 状态转移方程：
  - 当i!=0&&dp[i-1][j+1]>i-a时，dp[i][j]=dp[i-1][j+1]+1
  - 当i!=0&&dp[i-1][j+1]<i-a时，dp[i][j]=i-a;（其中a为从当前位置橫纵比较，在纵轴上找，找到的第一个不相等的x的位置,所以i-a就为最大的对称矩阵的长度）
  - 当i==0时，dp[i][j]=1;

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n;
string G[1005];
int dp[1005][1005];//dp[i][j]表示(i, j)为矩阵的左下角

int main()
{
    
    while(cin >> n && n)
    {
    
        getchar();
        for(int i=0; i<n; i++)
            getline(cin, G[i]);
        int ans = 0, a, b, len;
        for(int i=0; i<n; i++)
        {
    
            for(int j=0; j<n; j++)
            {
    
                if(i==0) dp[i][j] = 1;
                else
                {
    
                    a = i, b = j;//a是行，b是列
                    while(G[a][j]==G[i][b])
                    {
    
                        a--, b++;
                        if(a<0 || b>=n) break;
                    }
                    len = i-a;//对称的长度
                    if(len>dp[i-1][j+1]) dp[i][j] = dp[i-1][j+1]+1;
                    else                 dp[i][j] = len;
                }
                if(ans<dp[i][j]) ans = dp[i][j];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

R - Milking Time

题目链接：R - Milking Time

思路：我采用了LIS的状态构造思想。将区间按照结束时间从小到大排列。
- 状态构造：dp[i]表示以第i个区间为结束的可以获得的最大产量。
- 终态：max(dp[i])。
- 状态构造：dp[i] = max(dp[i], dp[j]+T[i].eff)，其中j<i且第j个区间的终止点一定与第i个区间的起始点保持R的距离。
- 初始化：dp[i] = T[i].eff。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 1005;
int N, M, R;
int dp[MAX];

struct Node
{
    
    int st, ed, eff;
    bool operator < (const Node &A) const
    {
    
        if(ed==A.ed) return st<A.st;
        else         return ed<A.ed;
    }
};
Node T[MAX];

int main()
{
    
    scanf("%d%d%d", &N, &M, &R);
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=M; i++)
    {
    
        scanf("%d%d%d", &T[i].st, &T[i].ed, &T[i].eff);
    }
    sort(T+1, T+M+1);
    for(int i=1; i<=M; i++)
        dp[i] = T[i].eff;
    int ans = dp[1];
    for(int i=2; i<=M; i++)
    {
    
        for(int j=1; j<i; j++)
        {
    
            if(T[j].ed+R<=T[i].st)
                dp[i] = max(dp[i], dp[j]+T[i].eff);
        }
        if(ans<dp[i]) ans = dp[i];
    }
    printf("%d\n", ans);
    return 0;
}

S - Making the Grade

题目链接：S - Making the Grade
参考博文：Making the Grade （线性+优化思维？）

思路：不断的优化，挺难想。
- 状态构造：dp[i][j]表示将第i个数变成第j小的数的最小代价，变完之后前i个数按序排列。
- 终态：min(dp[n][j])
- 状态转移方程：dp[i][j] = min(dp[i-1][k])+abs(a[i]-num[j]);（k<=j）其中a[i]表示第i个数的值，num[j]表示第j小的数的值。
- 初始化：dp[][] = 0。
  重点是代码的优化，变成了O(n^2)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int MAXN = 2005;
const int INF = 1<<30;//29位报错
int n;
int dp[MAXN],a[MAXN],b[MAXN],num[MAXN];

int get_ans(int a[], int num[])
{
    
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=n; i++)
    {
    
        int Min = INF;
        for(int j=1; j<=n; j++)//得到第i个数变成第j小的数的代价
        {
    
            Min = min(Min, dp[j]);//取第i-1个数变成第k(k<=j)小数的最小代价
            dp[j] = Min + abs(a[i]-num[j]);
        }
    }
    int ans = INF;
    for(int i=1; i<=n; i++) ans = min(ans, dp[i]);
    return ans;
}

int main()
{
    
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
    
        scanf("%d", &a[i]);
        num[i] = a[i];
        b[n-i+1] = a[i];//倒序
    }
    sort(num+1, num+n+1);
    printf("%d\n", min(get_ans(a, num), get_ans(b, num)));
    return 0;
}

本文链接：https://blog.csdn.net/Accept1234/article/details/100607510

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

什么是IOC和DI-程序员宅基地

文章浏览阅读553次。一、IOC是什么? IOC的英文名字是Inversion of Control，IOC即“控制反转”，不是什么技术，而是一种设计思想。在Java 开发中，Ioc意味着将你设计好的对象交给容器控制，而不是传统的在你的对象内部直接控制。 ①所谓控制，指的是管理对象的权利； ②所谓反转，指的是由Spring管理而不是开发者管理二、IOC的作用 IoC的其中一个目的是为了解耦合，当将一个对象交给第三方容器管理后，那么对象之间的耦合相较于传统 ne_ioc和di

Unity手机震动,Unity -＞ ios 震动_unity nice vibrations-程序员宅基地

文章浏览阅读2.1k次。说明Unity 有自己的接口 Handheld.Vibrate() 来实现手机的震动，这里来介绍下Unity调用ios原生震动。原生ios实现脚本下面有2个脚本都是震动的实现，用来自己测试。iOSHapticInterface.m与MultiHaptic.mm脚本。建议使用iOSHapticInterface.m脚本。iOSHapticInterface.m// This iOS haptic interface is a pretty straightforward impleme_unity nice vibrations

C语言中关于while语句的理解以及getchar和putchar_include<stdio.h>int main(){while(putchar(getchar()-程序员宅基地

文章浏览阅读888次，点赞32次，收藏9次。continue：跳过本次continue循环后面的代码，重新去判断部分（也就是重新进入while循环），看是否能够进行下一次循环。这串代码与上一次相比，我们把while中的条件改为了i_includeint main(){while(putchar(getchar())!='?'); return 0;}

74hc164驱动数码管c语言程序,74hc164应用电路图_74hc164驱动源程序-程序员宅基地

文章浏览阅读3.3k次。74hc164是高速硅门 CMOS 器件，与低功耗肖特基型 TTL (LSTTL) 器件的引脚兼容。74hc164是 8 位边沿触发式移位寄存器，串行输入数据，然后并行输出。数据通过两个输入端(DSA 或 DSB)之一串行输入；任一输入端可以用作高电平使能端，控制另一输入端的数据输入。两个输入端或者连接在一起，或者把不用的输入端接高电平，一定不要悬空。时钟 (CP) 每次由低变高时，数据右移一位，..._74hc164数码管

pyinstaller centos 打包记录_centos pyinstall-程序员宅基地

文章浏览阅读178次。报错2：error while loading shared libraries: libpython3.7m.so.1.0: cannot open shared object file: No such。报错1：OSError: Python library not found: libpython3.7mu.so.1.0, libpython3.7.so, l。添加库的配置信息，将python/lib的绝对路径（一般为：’/usr/python/lib’），添加至conf文件中。_centos pyinstall

linux下统计log中某个时间段的内出现某个关键字保存到文件_linux命令统计某个时间区间出现的关键字-程序员宅基地

文章浏览阅读674次。1、查看图中两个时间段内，且有“统计存储图片数据”的字段的日志 sed -n '/2021-06-03 11::25:34/,/2021-06-03 11:26:02/p' start.log |grep "统计存储图片数据" 注释： -n参数：只有经过sed特殊处理的那一行（或者动作）才会被显示 p参数：表示在终端打印出来 start.log：日志文件 grep: 对前面查询的结果进行过滤 "统计存储图片数据"：查询的关键字时间段：格式和日志保持一致，且时间值是真实存在的2、将时._linux命令统计某个时间区间出现的关键字

随便推点

使用Ajax实现简单的增删查改&&前端Ajax传的值，后端如何获取_ajax增删改查-程序员宅基地

文章浏览阅读4k次，点赞3次，收藏40次。实现查询和增删改一、Ajax最基本语法二、增删查改1.查询(Get请求)2.增删改(Post请求)三、后台(MVC/WebForm)1.MVC(Post请求)2.WebForm(Post请求)本人小白一个。其中所说可能有些不足，因为这些是我自己在写项目的过程中所使用的Ajax如有不对的地方，欢迎评论提出建议。一、Ajax最基本语法话不多说，直接上代码$.ajax({ url: "/User/GetUser",(这里写请求路径) type: "g_ajax增删改查

m4s格式转换mp4怎么转？只需3个步骤~-程序员宅基地

文章浏览阅读894次，点赞8次，收藏6次。无论您使用的是Windows、Mac还是Linux系统，主流播放器如VLC、Windows Media Player、QuickTime等都能轻松打开MP4文件，确保用户能够在各种平台上畅快观影。如果需要将M4S转换成MP4，野葱视频转换器为我们提供了便捷的解决方案，不仅具有稳定性，极少发生文件损坏，而且转换速度快，大大节约了时间。随着网络视频的普及，M4S通过分片存储音频和视频数据，提高了网络传输的效率，使得用户在观看视频时能够更加流畅地体验。处理完成后，你将在指定的输出路径中找到生成的MP4文件。_m4s格式转换mp4

CAN协议_为什么can诊断都是7开头-程序员宅基地

文章浏览阅读596次。网络管理报文（CAN 4开头，CAN FD 5开头），应用报文，诊断报文（7开头，物理寻址：一对一比如对单体安全访问，在线编程，功能寻址：服务需要一对多，保证ECU的状态相同，比如多个 ECU需要知道车速的信息，温度的信息）CAN_H的电平为3.5V，CAN_L线的电平为1.5V，CAN_H和CAN_L的电压差为2V左右，CAN_H和CAN_L线上的电压均为2.5v, CAN_H和CAN_L之间的电压差为0V。1、位错误：当总线赢得发送权后，会对总线电平进行侦听，当发送的电平和侦听的电平不一致；_为什么can诊断都是7开头