POJ 3666 Making the Grade DP

题意：给你n个数字，修改这些数字，以达到整个序列为非严格单调上升或下降的序列。

　　　求最少修改代价，代价为每个数字修改前后的差值。

　　　如1 3 2 4 5 3 9，让第2个数字3修改为2，代价为3-2=1，倒数第2个3修改为5，代价为5-3=2，总代价为2+1=3，所以最终的序列为 1 2 2 4 5 5 9，非严格上升序列

AC代码：

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2005;
const int INF = 0x3f3f3f3f;
int d[N][N],n,a[N],b[N],mx;
//d[i][j] 前i个数的序列，以第j个数为最后一个数的最小代价 
void solve()
{
	int ans = INF;
	
	sort(b+1,b+n+1);
	memset(d, 0, sizeof(d));
	
	for(int i = 1; i <= n; i++)
	{
		int mn = d[i-1][1];
		for(int j = 1; j <= n; j++)
		{
			mn = min(mn, d[i-1][j]);
			d[i][j] = mn + abs(b[j]-a[i]);
		}
	}
	
	for(int i = 1; i <= n; i++)
		ans = min(ans, d[n][i]);
	printf("%d
", ans);
}
int main()
{
	while(~scanf("%d", &n))
	{
		mx = 0;
		for(int i = 1; i <= n; i++)
			scanf("%d", a+i),b[i]=a[i];
		solve();
	}
	return 0;
}

AC代码（滚动数组）：

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2005;
const int INF = 0x3f3f3f3f;
int d[2][N],n,a[N],b[N],mx;
//d[i][j] 前i个数的序列，以第j个数为最后一个数的最小代价 
void solve()
{
	int ans = INF;
	
	sort(b+1,b+n+1);
	memset(d, 0, sizeof(d));
	int f = 0;
	
	
	for(int i = 1; i <= n; i++)
	{
		int mn = d[f][1];
		for(int j = 1; j <= n; j++)
		{
			mn = min(mn, d[f][j]);
			d[!f][j] = mn + abs(b[j]-a[i]);
		}
		f = !f;
	}
	
	for(int i = 1; i <= n; i++)
		ans = min(ans, d[f][i]);
	printf("%d
", ans);
}
int main()
{
	while(~scanf("%d", &n))
	{
		mx = 0;
		for(int i = 1; i <= n; i++)
			scanf("%d", a+i),b[i]=a[i];
		solve();
	}
	return 0;
}

POJ 3666 Making the Grade DP

相关推荐