【DP】노면수정usaco 2008febgold

제목 설명:
```
FJ는 농장에 있는 울퉁불퉁한 흙길을 잘 보수할 계획이다.젖소들의 요구에 따라 수리한 노면의 높이는 단조롭게 상승하거나 단조롭게 하락해야 한다. 즉, 높이 상승과 높이 하락의 구간은 수리한 노면에 동시에 나타나서는 안 된다.
길 전체가 N단으로 나뉘었고 N개의 정수 A1, ... , A_N(1 <= N <= 2000)은 각 세그먼트의 높이(0 <= A i <= 1000000000)를 차례로 설명합니다.FJ는 N개의 원소가 꼭 포함된 상승하지 않거나 하락하지 않는 서열 B 를 찾고 싶어 한다1, ... , B_N, 수리한 길의 각 구간의 높이로 한다.각 구간의 도로 매트리스를 높이거나 낮은 단위를 파는 비용이 같기 때문에 도로 보수의 총 지출은 다음과 같이 나타낼 수 있다.
      |A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|
FJ의 이 공사에서의 최소 지출이 얼마인지 계산해 보십시오.FJ는 당신에게 이 지출이 2^31-1을 초과하지 않을 것을 보증합니다.
```
 
제목 대의: 상승하지 않거나 하락하지 않는 서열로 수정하여 수정 비용을 최대한 적게 할 수 있도록 수열을 제시합니다.수정된 비용은 수정 후 수정 전의 값과 차이의 절대값으로 정의됩니다.
 
오르지 않으면 역순+내리지 않기 때문에 내리지 않는 것만 생각하면 된다.우선 수조를 작은 것부터 큰 것까지 s로 정렬하고 f[i][j]로 전 i개수가 조건을 충족시키는 경우 다음 i개수를 s[j]의 최소 비용으로 수정한다.상태 전이 방정식은 f[i][j]=min{f[i-1][k]+abs(s[k]-num[i])|j<=n}이다.그러나 이러한 시간 복잡도는 O(n^3)이기 때문에 전략을 바꿔야 한다.
f[i][j]로 전 i개수가 모두 조건을 충족시켰음을 표시하면 다음 i개수는 s[j]와 같은 최소 비용보다 작다.상태 전이 방정식은 f[i][j]=min{f[i][j-1], f[i-1][j]+abs(s[j]-num[i])}이다.시간의 복잡도가 O(n^2)로 떨어졌다.
 
코드:
 

#include
#include
#include
using namespace std;

const int inf = (1 << 30);

int n, a[2005], b[2005], s[2005], f[2005][2005], ans;

void dp(int *A) {
	memset(f, 0, sizeof f);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(j == 1)
				f[i][j] = f[i-1][j] + abs(A[i] - s[j]);
			else
				f[i][j] = min(f[i][j-1], f[i-1][j] + abs(A[i] - s[j]));
			if(i == n) ans = min(ans, f[i][j]);
		}
	}
}

int main () {
	
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]), s[i] = a[i], b[n - i + 1] = a[i];
	sort(s + 1, s + n + 1);
	ans = inf; dp(a); dp(b);
	printf("%d
", ans);
}