poj3666

maksyuki 发表于 oj 分类，标签: DP-线性DP

11 2月 2017

Making the Grade

A straight dirt road connects two fields on FJ's farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down).

You are given N integers A₁, ... , A_N (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ A_i ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B₁, . ... , B_N that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is

|A₁- B₁| + |A₂- B₂| + ... + |A_N - B_N |

Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer elevation: A_i

Output

* Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation.

Sample Input

Sample Output

Source

USACO 2008 February Gold

题目类型：线性DP

算法分析：dp[i][j]表示前i个数字且最后数字是第j小的最小改动量，这里有一个贪心思想是一个数字改动成相邻两个数字的值的时候才能构成最小改动量。初始化dp[1][0] = a[1] - b[i]，其中在非递减序列中b[i]为a[i]递增排序后的值，状态转移方程为dp[i][j] = min(dp[i-1][k]) + abs(a[i] - b[j]) k=1->j，由于min(dp[i-1][k]) = min(dp[i-1][1], dp[i-1][2], … dp[i-1][j])，而dp[i-1][1]当i==2时是已知的，所以可以利用前缀性质优化求解k所在的循环，最后循环更新最大值即可

/**************************************************
filename       :e.cpp
author         :maksyuki
created time   :2017/2/11 18:50:59
last modified  :2017/2/11 19:09:44
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CPPFF ifstream cin ("in")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int a[2000+6], b[2000+6];
int dp[2][2000+6];

int main()
{
    //CFF;
    //CPPFF;
    int n;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        
        sort(b + 1, b + 1 + n);
        for(int i = 1; i <= n; i++)
            dp[1&1][i] = abs(a[1] - b[i]);

        for(int i = 2; i <= n; i++)
        {
            int minval = INF;
            for(int j = 1; j <= n; j++)
            {
                minval = min(minval, dp[(i-1)&1][j]);
                dp[i&1][j] = minval + abs(a[i] - b[j]);
            }
        }

        int res = INF;
        for(int i = 1; i <= n; i++)
            res = min(res, dp[n&1][i]);
        
        sort(b + 1, b + 1 + n, greater<int>());
        for(int i = 1; i <= n; i++)
            dp[1&1][i] = abs(a[1] - b[i]);

        for(int i = 2; i <= n; i++)
        {
            int minval = INF;
            for(int j = 1; j <= n; j++)
            {
                minval = min(minval, dp[(i-1)&1][j]);
                dp[i&1][j] = minval + abs(a[i] - b[j]);
            }
        }

        for(int i = 1; i <= n; i++)
            res = min(res, dp[n&1][i]);

        printf("%d\n", res);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

/**************************************************

filename :e.cpp

author :maksyuki

created time :2017/2/11 18:50:59

last modified :2017/2/11 19:09:44

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CPPFF ifstream cin ("in")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int a[2000+6], b[2000+6];

int dp[2][2000+6];

int main()

{

//CFF;

//CPPFF;

int n;

while(scanf("%d", &n) != EOF)

{

for(int i = 1; i <= n; i++)

{

scanf("%d", &a[i]);

b[i] = a[i];

}

sort(b + 1, b + 1 + n);

for(int i = 1; i <= n; i++)

dp[1&1][i] = abs(a[1] - b[i]);

for(int i = 2; i <= n; i++)

{

int minval = INF;

for(int j = 1; j <= n; j++)

{

minval = min(minval, dp[(i-1)&1][j]);

dp[i&1][j] = minval + abs(a[i] - b[j]);

}

int res = INF;

for(int i = 1; i <= n; i++)

res = min(res, dp[n&1][i]);

sort(b + 1, b + 1 + n, greater<int>());

for(int i = 1; i <= n; i++)

dp[1&1][i] = abs(a[1] - b[i]);

for(int i = 2; i <= n; i++)

{

int minval = INF;

for(int j = 1; j <= n; j++)

{

minval = min(minval, dp[(i-1)&1][j]);

dp[i&1][j] = minval + abs(a[i] - b[j]);

}

for(int i = 1; i <= n; i++)

res = min(res, dp[n&1][i]);

printf("%d\n", res);

}

return 0;

}

poj1548

poj2392

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

poj3666

分类目录

标签云

书签

近期评论