poj3666（DP+离散化）

约定不等于承诺〃 2021-12-21 01:05 255阅读 0赞

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

思路：

看了讨论区说本题的数据比较弱，只需要考虑不减序列即可，比较懒，所以我也只写了这一部分的代码，思路都一样，能AC就行了。

首先要想明白一点，就是将每一个elevation更新后的值一定是原来存在的，因为更新一个elevation最好是与前一个相等，要么与后一个相等，可以从贪心角度去想，这里要先明白，很重要。所以我们将原始数据存在a数组中，将a数组按升序排序后存在b中。用dp\[i\]\[j\]表示a数组前i个数据中最后一个数据是b\[j\]的最小代价，则状态转移方程即为：dp\[i\]\[j\]=dp\[i-1\]\[k\]+abs(b\[j\]-a\[i\]) (k<=j)。因为求dp\[i\]\[j\]时只会用到dp\[i-1\]\[k\]，所以可以用滚动数组，使空间大大节省。详见代码：

1 #include<cstdio>
     2 #include<algorithm>
     3 using namespace std;
     4 
     5 int n,res=0x3f3f3f3f;
     6 int a[2005],b[2005],dp[2005];
     7 
     8 int main(){
     9     scanf("%d",&n);
    10     for(int i=1;i<=n;++i){
    11         scanf("%d",&a[i]);
    12         b[i]=a[i];
    13     }
    14     sort(b+1,b+n+1);
    15     for(int i=1;i<=n;++i){
    16         int tmp=0x3f3f3f3f;
    17         for(int j=1;j<=n;++j){
    18             tmp=min(tmp,dp[j]);
    19             dp[j]=tmp+abs(b[j]-a[i]);
    20         }
    21     }
    22     for(int i=1;i<=n;++i)
    23         res=min(res,dp[i]);
    24     printf("%d\n",res);
    25     return 0;
    26 }

转载于:https://www.cnblogs.com/FrankChen831X/p/10449459.html

发表评论取消回复

表情：

评论列表（有 0 条评论，255人围观）

还没有评论，来说两句吧...

相关阅读

相关 #51 D. Beautiful numbers （数位dp+离散化）

题目链接: [点击打开链接][Link 1] http://codeforces.com/contest/55/problem/D 题意：定义：Beaut

小咪咪/ 2022年06月17日 03:44/ 0 赞/ 181 阅读

相关【dp】Making the Grade POJ - 3666

Think: 1知识点：dp+sort()快速排序 2状态转移方程 dp[i][j]:i个数以b[j]作为第i个数的当前状态最优解; dp[i][j]

谁践踏了优雅/ 2022年06月10日 05:27/ 0 赞/ 110 阅读

相关【数位DP+离散化】Beautiful numbers CodeForces - 55D

Think: 1知识点：数位DP(+记忆化搜索)+离散化 2题意：输入一个区间，询问在这个区间内有多少个beautiful number，a positive inte

àì夳堔傛蜴生んèń/ 2022年06月08日 11:20/ 0 赞/ 188 阅读

相关 CodeForces - 714E + POJ - 3666 （dp严格单调递增与非严格单调递增）

POJ - 3666 ：此题是dp非严格单调递增的最小花费，要满足非严格递增，即后一个要大于等于前一个数，现在要求n个数的非严格递增前i个数的花费肯定是前i-1个数花费，再

本是古典何须时尚/ 2022年05月23日 04:20/ 0 赞/ 190 阅读

相关 HDU 6365 Shoot Game区间dp+离散化

[传送门][Link 1] 这个题跟UVALive - 6938，的思路是一样的，感觉没做过那个题，这个题真的不好想。具体思路可以看 [\-》这个题][-] 然后这个题就

叁歲伎倆/ 2022年05月17日 12:11/ 0 赞/ 183 阅读

相关 UVALive - 6938 区间dp+离散化

[传送门][Link 1] 思路：一条射线最小的花费就是路径上最高的那个，对于时间这个区间，我们可以将其离散化成1~600的范围，因为有三百个点，最多就600个不同的数，转移

小鱼儿/ 2022年05月17日 12:09/ 0 赞/ 151 阅读

相关 POJ 2528 线段树+离散化

[POJ 2528][] 关键在于插入数据的顺序------从上往下依次插入每张海报，这样后插入的海报不可能覆盖先插入的海报，因此插入一张海报时，如果发现海

朱雀/ 2022年03月29日 06:00/ 0 赞/ 250 阅读

相关 poj3666（DP+离散化）

题目链接：http://poj.org/problem?id=3666 思路：看了讨论区说本题的数据比较弱，只需要考虑不减序列即可，比较懒，所以我也只写了这一部分的代码，

约定不等于承诺〃/ 2021年12月21日 01:05/ 0 赞/ 256 阅读

相关 POJ3666 Making the Grade（dp+离散化）

题意：《算法竞赛进阶指南》P267-268。分析：《算法竞赛进阶指南》P268-269。代码（方法二）： include<iostream>

落日映苍穹つ/ 2021年11月26日 14:20/ 0 赞/ 227 阅读

相关 Poj 3581 Sequence (离散化+后缀数组)

题意：给定一个数列，将其分为非空的三段。然后分别将三段的数字翻转连接在一起组成新的数列。输出处理后字典序最小的结果。思路：首先注意必须写成单Case的形式！！！[while

古城微笑少年丶/ 2021年11月11日 01:40/ 0 赞/ 257 阅读