当前位置 博文首页 > 文章内容

    POJ3666 - Making the Grade - 简单DP+滚动数组

    作者: 栏目:未分类 时间:2020-09-25 9:00:45

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    题意

    先给出了一个\(n\),之后给出\(n\)个数,

    要求通过改变一些数,使得最后变成有序的序列(增或减),输出最小的修改量。

    思路

    二维DP+滚动数组。

    因为数据较弱,所以不用严格递增或严格递减,所以序列中的高度一定是出现过的高度。

    所以,最终修改后,或者和前一个数字一样,或者和后一个数字一样,这样才能使修改量最小。

    所以先排序,

    dp[i][j]:表示前\(i\)个元素,最后元素为序列中第\(j\)小元素的最优解。

    AC代码

    #include<iostream>
    #include<string.h>
    #include<algorithm>
    #include<stdio.h>
    #include<cmath>
    #include<list>
    #include<stdlib.h>
    #include<map>
    #include<vector>
    #include<stack>
    #include<stdio.h>
    #include<queue>
    using namespace std;
    typedef long long ll;
    #define sc(T) scanf("%d",&T)
    #define scc(x,y) scanf("%d %d",&x,&y)
    #define pr(T) printf("%d\n",T)
    #define f(a,b,c) for (int a=b;a<c;a++)
    #define ff(a,b,c) for (int a=b;a>c;a--)
    #define inf 0x3f3f3f3f
    #define mem(a,b) memset(a,b,sizeof(a))
    #define eps 1e-9
    #define PI acos(-1)
    
    const int N=2010;
    int a[N],b[N],dp[2][N];
    
    int main()
    {
        int n;
        sc(n);
        for(int i=1; i<=n; i++)
            sc(a[i]),b[i]=a[i];
        sort(b+1,b+1+n);
        for(int i=1; i<=n; i++)
            dp[0][i]=abs(a[1]-b[i]);
        for(int i=2; i<=n; i++)
        {
            int k=dp[i%2][1];
            for(int j=1; j<=n; j++)
            {
                k=min(k,dp[i%2][j]);
                int t=abs(a[i]-b[j]);
                dp[(i+1)%2][j]=k+t;
            }
        }
        int kk=(n+1)%2,w=dp[kk][1];
        for(int i=2; i<=n; i++)
            w=min(w,dp[kk][i]);
        pr(w);
        return 0;
    }