首页 > 其他 > 详细

poj3666序列对应——DP

时间:2018-03-13 23:29:01      阅读:303      评论:0      收藏:0      [点我收藏+]

题目:http://poj.org/problem?id=3666

很普通的DP,离散化(sort)一下即可;

mn的求法很不错(比我原来开了mn[]……简洁)。

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,a[2005],l[2005],f[2005][2005],ans,mn,INF=1000000005;
int main()
{
    memset(f,2,sizeof f);
    ans=INF;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memcpy(l,a,sizeof a);
    sort(l+1,l+n+1);
    for(int i=1;i<=n;i++)
        f[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        mn=INF;
        for(int j=1;j<=n;j++)
        {
            mn=min(mn,f[i-1][j]);
            f[i][j]=mn+abs(a[i]-l[j]);
        }
    }
    for(int i=1;i<=n;i++)
        ans=min(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

 

poj3666序列对应——DP

原文:https://www.cnblogs.com/Zinn/p/8563559.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!