poj-3666

题目是dp 题目; 简单dp 离散一下就好.

我们先来讲一讲不离散的,简单的懂了,其他的也很容易. dp[i] 代表这个数列以i 结尾的最小花费; 假设现在要求前n个数组成的数列,那么dp[i]= 前 n-1 的 min(dp[i]~dp[0])+ (当前这个数-i);

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const int MOD=1e9+7;

const int MAXSIZE=1e6+5;

const double eps=0.0000000001;

void fre()

{

    freopen("in.txt","r",stdin);

    freopen("out.txt","w",stdout);

}

#define memst(a,b) memset(a,b,sizeof(a))

#define fr(i,a,n) for(int i=a;i<n;i++)

const int MAXN=2010;

int a[MAXN],index[MAXN];

int dp[MAXN],temp[MAXN];

bool cmp(int x,int y)

{

	return a[x]<a[y];

}

int solve(int n)

{

	for(int i=0;i<n;i++) temp[i]=abs(a[0]-a[index[i]]);

	for(int k=0;k<n-1;k++)

	{

		int minnum=INF;

		for(int i=0;i<n;i++)

		{

			minnum=min(minnum,temp[i]);

			dp[i]=abs(a[k+1]-a[index[i]])+minnum;

		}

		for(int i=0;i<n;i++) temp[i]=dp[i];

	}

    int res=INF;

    for(int i=0;i<n;i++)

    	res=min(res,dp[i]);

    return res;

}

int main(int argc,char *argv[])

{

	int n;

	while(scanf("%d",&n)+1)

	{

		for(int i=0;i<n;i++)

			scanf("%d",&a[i]),index[i]=i;

		sort(index,index+n,cmp);

		printf("%d\n",solve(n));

	}

    return 0;

}

/**************************************************/

/**             Copyright Notice                 **/

/**  writer: wurong                              **/

/**  school: nyist                               **/

/**  blog  : http://blog.csdn.net/wr_technology  **/

/**************************************************/

巴特西

poj-3666

最新文章

热门文章