POJ_3666_Making_the_Grade_(动态规划)

描述

给一串坡的高度,现在要调整某些点,使整个坡单调不降或单调不升.调整的花费为原高度与先高度的差的绝对值,问最小花费(可单增可单降).

Making the Grade

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5802		Accepted: 2717

Description

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[i][j]表示前i个点有序且以j结尾的最小花费.则有转移方程:

dp[i][j]=min(dp[i-1][k])+abs(a[i]-j) (0<=k<=j).

但是看数据范围发现高度可以取到10^9,而且分析可知,一个点如果需要调整,为了花费最小,只需要和左边一样就好,所以调整之后的取值一定在a数组中,显然要离散一下.

用dp[i][j]表示前i个点有序且以b[i]结尾的最小花费.则有转移方程:

dp[i][j]=min(dp[i-1][k])+abs(a[i]-a[j])(a[k]<=a[j]).

这样的话就需要三层i,j,k的循环,会超时,考虑把a数组copy一份到b,然后把b升序排列一下,这样在第二层循环里统计k<=j即b[k]<=b[j]的最小的dp[i-1][k].另外,由于只用到了i和i-1,所以可以考虑使用滚动数组.

ps.

1.POJ上数据有问题,单调不降一遍就能过,实际上应该dp两遍.

2.感觉自己好弱啊,动规基本都是看题解才做出来的= =,我这样强行作死真的大丈夫?

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define for1(i,a,n) for(int i=(a);i<=(n);i++)
 6 #define read(a) a=getnum()
 7 #define CC(i,a) memset(i,a,sizeof(i))
 8 using namespace std;
 9 
10 const int maxn=2000+5,INF=0x7fffffff;
11 int n;
12 int a[maxn],b[maxn];
13 int dp[2][maxn];
14 
15 inline int getnum()
16 {
17     int r=0,k=1; char c;
18     for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') k=-1;
19     for(;c>='0'&&c<='9';c=getchar()) r=r*10+c-'0';
20     return r*k;
21 }
22 
23 bool comp(int a,int b) { return a>b; }
24 
25 void solve()
26 {
27     sort(b+1,b+n+1);
28     for1(i,1,n) dp[1][i]=abs(a[1]-b[i]);
29     for1(i,2,n)
30     {
31         int min_c=dp[(i-1)&1][1];
32         for1(j,1,n)
33         {
34             min_c=min(min_c,dp[(i-1)&1][j]);
35             dp[i&1][j]=min_c+abs(a[i]-b[j]);
36         }
37     }
38     int ans=INF;
39     for1(i,1,n) ans=min(ans,dp[n&1][i]);
40     sort(b+1,b+n+1,comp);
41     for1(i,1,n) dp[1][i]=abs(a[1]-b[i]);
42     for1(i,2,n)
43     {
44         int min_c=dp[(i-1)&1][1];
45         for1(j,1,n)
46         {
47             min_c=min(min_c,dp[(i-1)&1][j]);
48             dp[i&1][j]=min_c+abs(a[i]-b[j]);
49         }
50     }
51     for1(i,1,n) ans=min(ans,dp[n&1][i]);
52     printf("%d
",ans);
53 }
54 
55 void init()
56 {
57     read(n);
58     for1(i,1,n)
59     {
60         read(a[i]);
61         b[i]=a[i];
62     }
63 }
64 
65 int main()
66 {
67 #ifndef ONLINE_JUDGE
68     freopen("making.in","r",stdin);
69     freopen("making.out","w",stdout);
70 #endif
71     init();
72     solve();
73 #ifndef ONLINE_JUDGE
74     fclose(stdin);
75     fclose(stdout);
76     system("making.out");
77 #endif
78     return 0;
79 }
80         
81         
82

View Code