福州网站建设公司哪家好,横沥镇做网站,安徽建设工程网,wordpress将首页转成html题意#xff1a;
给你n个山的高度#xff0c;单独的一个数可以任意加减#xff0c;让经过对每座山峰任意加减高度后变成递增或递减的序列时#xff0c;求对每个数的相加或相减的数目的最小和。
题目#xff1a;
A straight dirt road connects two fields on FJ’s far…题意
给你n个山的高度单独的一个数可以任意加减让经过对每座山峰任意加减高度后变成递增或递减的序列时求对每个数的相加或相减的数目的最小和。
题目
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 A1, … , AN (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ Ai ≤ 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 B1, . … , BN 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
|A1 - B1| |A2 - B2| … |AN - BN | 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: NLines 2…N1: Line i1 contains a single integer elevation: Ai
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
7 1 3 2 4 5 3 9
Sample Output
3
分析
前言这道题纠结了好久原因是我没想到离散化知道用离散化后我还是转不过来认为经过增加或减少后山峰的高度不为原始高度的任意一种所以认为离散化不是最优的其实到现在我还是这么认为但由于山峰高度过高哪怕离散化过后枚举复杂度还是有o(n2n^{2}n2),所以我妥协了在这里求助如果有大犇有关于这道题离散化更好地理解希望能给我一些帮助嘻嘻 1.这道题dp还是好理解的即离散化过后每次枚举当第i个山峰到达某山峰高度dp[i][j]表示把前i个数变成单调增且第i个数变成原来第j大的数的最小代价。 2、把给定的山峰高度排好序就成为其离散的递增或递减的高度。 3、对第一点进行与排好序的最小值的点进行比较求得dp[0][j]要升到第j的高度时所要的花费 4、对第二点及以后的每一点进行更新。dp[i][j]第i1点到高度j时的前i1个总的花费 5、找到更后最后一个点到任意高度的最小值便为答案
AC代码
#includestring.h
#includestdio.h
#includeiostream
#includealgorithm
using namespace std;
const int M2e310;
int n,k;
int a[M],b[M],c[M];
int dp[M][M],e[M][M];///用数组下标进行离散化表示某位置最小的花费
bool cmp(int x,int y)
{return xy;
}
int main()
{cinn;for (int i0; in; i)cina[i],b[i]c[i]a[i];sort(b,bn);for (int i0; in; i)dp[0][i]abs(b[i]-a[0]);for(int i1; in; i)//枚举第几座山峰{kdp[i-1][0];for (int j0; jn; j)///枚举山峰到达离散化后某高度{kmin(k,dp[i-1][j]);dp[i][j]kabs(b[j]-a[i]);}}sort(c,cn,cmp);for (int i0; in; i)e[0][i]abs(c[i]-a[0]);for(int i1; in; i){ke[i-1][0];for (int j0; jn; j){kmin(k,e[i-1][j]);e[i][j]kabs(c[j]-a[i]);}}int ansdp[n-1][0];for (int i0; in; i)ansmin(ans,min(dp[n-1][i],e[n-1][i]));coutansendl;return 0;
}
