【dp】Making the Grade POJ - 3666

谁践踏了优雅 2022-06-10 05:27 118阅读 0赞

Think:  
1知识点：dp+sort()快速排序  
2状态转移方程

dp[i][j]:i个数以b[j]作为第i个数的当前状态最优解;
    dp[i][j] = abs(a[i]-b[j]) + min(dp[i-1][k]) 1<=k<=n;

3思考：可通过滚动数组优化

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 2014;
    
    int a[N], b[N], dp[N][N];
    /*dp[i][j]:i个数以b[j]作为第i个数的当前最优解*/
    
    void solve(int n);
    
    int main(){
        int n, i;
        while(~scanf("%d", &n)){
            for(i = 1; i <= n; i++){
                scanf("%d", &a[i]);
                b[i] = a[i];
            }
            solve(n);
        }
        return 0;
    }
    void solve(int n){
        sort(b+1, b+1+n);
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++){
            int miv = dp[i-1][1];
            for(int j = 1; j <= n; j++){
                miv = min(miv, dp[i-1][j]);
                dp[i][j] = miv + abs(a[i]-b[j]);
            }
        }
        int ans = inf;
        for(int i = 1; i <= n; i++)
            ans = min(ans, dp[n][i]);
        printf("%d\n", ans);
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 <poj-1611>The Suspects

The Suspects <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

忘是亡心i/ 2022年07月15日 08:56/ 0 赞/ 145 阅读

相关 POJ 1163 The Triangle

Description 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

素颜马尾好姑娘i/ 2022年06月10日 12:44/ 0 赞/ 161 阅读

相关【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 赞/ 119 阅读

相关 poj--1611--The Suspects

The Suspects <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

我会带着你远行/ 2022年06月10日 00:19/ 0 赞/ 154 阅读

相关 POJ - 1611 - The Suspects

-------------------- 题目连接：[http://poj.org/problem?id=1611][http_poj.org_problem_id_1611

柔光的暖阳◎/ 2022年06月10日 00:09/ 0 赞/ 173 阅读

相关 POJ 1556-The Doors

The Doors <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

约定不等于承诺〃/ 2022年03月26日 05:42/ 0 赞/ 129 阅读

相关 POJ-1611—The Suspects

[1611–The Suspects][1611_The Suspects] Description Severe acute respiratory syndro

客官°小女子只卖身不卖艺/ 2022年03月09日 01:10/ 0 赞/ 197 阅读

相关 Making the Grade

[Making the Grade][] 给定长度为n的序列\\(\\\{a\_i\\\}\\),求构造长度为n的递增序列\\(\\\{b\_i\\\}\\)，求\\(\\s

妖狐艹你老母/ 2022年01月08日 00:25/ 0 赞/ 190 阅读

相关 poj3666（DP+离散化）

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

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

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

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

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