11282: 【原1282】修路

题目描述

author: Chen Xutong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1282

Description

|A1-B1|+|A2-B2|+…..+|An-Bn|

Sample Input

``````7
1
3
2
4
5
3
9
``````

Sample Output

``````3
``````

ligongzzz's solution

``````#include "iostream"
#include "cmath"
#include "algorithm"
using namespace std;

int n, ans = 1e9, a[2009], c[2009],
f[2009][2009], g[2009][2009];

void sol()
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
f[i][j] = g[i - 1][j] + abs(a[i] - c[j]);
if (j == 1)
g[i][j] = f[i][j];
else
g[i][j] = min(f[i][j], g[i][j - 1]);
}
}
for (int i = 1; i <= n; ++i)
ans = min(ans, f[n][i]);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

//输入并排序
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
c[i] = a[i];
}
sort(c + 1, c + n + 1);

sol();
//反序
for (int i = 1; i <= n / 2; ++i)
swap(c[i], c[n - i + 1]);

sol();
cout << ans;

return 0;
}
``````

Neight99's solution

``````#include <cmath>
#include <iostream>

using namespace std;

const int maxN = 2000 + 100;

long long ans = 1e17, height[maxN] = {0}, height1[maxN] = {0},
dp[maxN][maxN] = {0};

void qSort(long long *, int, int);
void DP(int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n;

cin >> n;
for (int i = 0; i < n; i++) {
cin >> height[i];
height1[i] = height[i];
}
qSort(height1, 0, n - 1);
DP(n);
cout << ans;

return 0;
}

void qSort(long long *nums, int l, int h) {
if (l >= h) {
return;
}
int first = l, last = h;
long long key = nums[first];

while (first < last) {
while (first < last && nums[last] >= key) {
--last;
}
nums[first] = nums[last];
while (first < last && nums[first] <= key) {
++first;
}
nums[last] = nums[first];
}
nums[first] = key;
qSort(nums, l, first - 1);
qSort(nums, first + 1, h);
}

void DP(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) {
if (j == 0) {
dp[i][j] = abs(height1[j] - height[i]);
} else {
dp[i][j] = min(abs(height1[j] - height[i]), dp[i][j - 1]);
}
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] + abs(height1[j] - height[i]);
} else {
dp[i][j] = min(dp[i - 1][j] + abs(height1[j] - height[i]),
dp[i][j - 1]);
}

if (i == n - 1) {
ans = min(ans, dp[i][j]);
}
}
}

for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (i == n - 1) {
if (j == 0) {
dp[i][j] = abs(height1[j] - height[i]);
} else {
dp[i][j] = min(abs(height1[j] - height[i]), dp[i][j - 1]);
}
} else if (j == 0) {
dp[i][j] = dp[i + 1][j] + abs(height1[j] - height[i]);
} else {
dp[i][j] = min(dp[i + 1][j] + abs(height1[j] - height[i]),
dp[i][j - 1]);
}

if (i == 0) {
ans = min(ans, dp[i][j]);
}
}
}

return;
}
``````

WashSwang's solution

``````#include <iostream>
#include <cstring>
using namespace std;
int n,h[3000],o[3000];
long long dps[2001][2001],dpt[2001][2001],mins,mint;
void qsort(int *s,int *t){
if (s+1>=t) return;
int i=0,j=int(t-s)-1,x=s[0];
while (i<j){
while (i<j&&s[j]>=x) j--;
if (i<j) s[i++]=s[j];
while (i<j&&s[i]<=x) i++;
if (i<j) s[j--]=s[i];
}
s[i]=x;
qsort(s,s+i);
qsort(s+i+1,t);
}
int main() {
cin>>n;
for (int i=1;i<=n;++i){
cin>>h[i];
o[i]=h[i];
}
qsort(o+1,o+n+1);
for (int i=1;i<=n;++i) {
mins=1e12;
for (int j = 1; j <= n; ++j){
if (dps[i-1][j]<mins) mins=dps[i-1][j];
dps[i][j]=mins+abs(h[i]-o[j]);
}
mint=1e12;
for (int j = n; j>=1;--j){
if (dpt[i-1][j]<mint) mint=dpt[i-1][j];
dpt[i][j]=mint+abs(h[i]-o[j]);
}
}
mins=1e12;
mint=1e12;
for (int i=1;i<=n;++i)
{
mins=min(dps[n][i],mins);
mint=min(dpt[n][i],mint);
}
cout<<min(mins,mint);
return 0;
}
``````