第七届河南省程序设计大赛——D 山区修路（动态规划）

小灰灰 2022-04-25 05:04 220阅读 0赞

## 题目描述: ##

某山区的孩子们上学必须经过一条凹凸不平的土路，每当下雨天，孩子们非常艰难。现在村里走出来的Dr. Kong决定募捐资金重新修建着条路。由于资金有限，为了降低成本，对修好后的路面高度只能做到单调上升或单调下降。

为了便于修路，我们将整个土路分成了N段，每段路面的高度分别A1，A2,….,An。由于将每一段路垫高或挖低一个单位的花费成本相同，修路的总费用与路面的高低成正比。

现在Dr. Kong希望找到一个恰好含N个元素的不上升或不下降序列B1，B2,….,Bn，作为修过的路路段的高度。要求：

| A1-B1| + | A2–B2| + ... + | An-Bn|------>最小

## 输入描述: ##

第一行： K                            表示有多少组测试数据。
    接下来对每组测试数据：
    第1行:       N                表示整个土路分成了N段
    第2~N+1行： A1  A2 ……AN     表示每段路面的高度
    2≤k≤10      0≤Ai≤10000000    0≤N≤500    (i=1,…, N)
    所有数据都是整数。 数据之间有一个空格。
    数据保证| A1-B1|+| A2-B2|+ ... +| An-Bn|的最小值不会超过109

## 输出描述: ##

对于每组测试数据，输出占一行：| A1-B1|+| A2-B2|+ ... +| An-Bn|的最小值。

## 样例输入: ##

复制

2
    7
    1 3 2 4 5 3 9
    5
    8 6 5 6 2

## 样例输出: ##

3
    1

变形的动态规划，无奈自己太菜，思路是看的别人的，

dp\[i\]\[j\]代表第i个山头变化到j值时需要的花费

m数组表示输入的山头的高，n数组是将m数组按照山头高度重排后的数组

dp\[i\]=abs（m\[i\]-n\[j\]）+num（num代表从0到j的最小花费）

ac代码：

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    #define INF 99999999
    using namespace std;
    int N,n[501],m[501],dp[501][501];
    bool cmp(int a,int b){
    	return a>b;
    }
    int solve(){
    	for(int i=1;i<=N;i++)dp[1][i]=abs(m[1]-n[i]);
    	for(int i=2;i<=N;i++){
    		int num=INF;
    		for(int j=1;j<=N;j++){
    			num=min(num,dp[i-1][j]);
    			dp[i][j]=abs(m[i]-n[j])+num;
    		}
    	}
    	int num=INF;
    	for(int i=1;i<=N;i++){
    		num=min(num,dp[N][i]);
    	} 
    	return num;
    }
    int main()
    {
    	int k;
    	cin>>k; 
    	while(k--){
    		cin>>N;
    		for(int i=1;i<=N;i++){
    			cin>>m[i];
    			n[i]=m[i];
    		}
    		int t1,t2;
    		sort(n+1,n+N+1);
    		t1=solve();
    		sort(n+1,n+N+1,cmp);
    		t2=solve();
    		cout<<min(t1,t2)<<endl;
    	}
    	return 0;
    }