poj3666(dp逻辑的重要性)

思路：不知道为啥中间有一段时间没搞清楚状态时怎么转移的，想了好久，不过最后还是想明白了。在想状态转移的时候一定要牢牢抓住状态，通过状态来思考如何转移；第一次提交得到了完美的TLE，因为复杂度是n^3(其实当时也想到了，不过抱着侥幸的心理提交了)；上网查了查题解，别的都是一样的，就在判断最小dp值时，每次都历遍造成了重复计算，优化一下，每次都记录最小值minn，那么后面一个直接跟minn比，就得到了最小值，附上两份代码；

AC代码如下：

/*
最优子结构：dp[i][j]第i个数以第j大的数作为结尾得到的非严格递增(递减)子序列的最小花费 
子问题:min((dp[i-1][k]|1<=k<=j))+num[i]-hash[j] hash[j]:第j大的数的值
如果按照上面的思路代码是n3的复杂度，可以优化，因为可以每次记录当前最小的值，拿这个值跟后面一个比较就可以得到最小值
这题数据比较差，直接算非严格递增子序列就能ac； 
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 2055
#define inf 1000000000
int dp[maxn][maxn]; 
int hash[maxn];
int num[maxn];
int temp1[maxn];
int main()
{
	int n;
	scanf(\"%d\",&n);
	for(int i=1;i<=n;i++)
	{
		scanf(\"%d\",&num[i]);
		temp1[i]=num[i];
	} 
	sort(temp1+1,temp1+1+n);
	int count=2;
	hash[1]=temp1[1];
	for(int i=2;i<=n;i++)
	{
		if(temp1[i]!=temp1[i-1])
			hash[count++]=temp1[i];//把temp[i]映射成count 
	}
	count--;
	/*for(int i=1;i<=count;i++)
	{
		printf(\"%d->%d \",hash[i],i);
	}
	printf(\"\\n\");*/
	for(int i=1;i<=n;i++)//第i个数 
	{
		int minn=dp[i-1][1];
		for(int j=1;j<=count;j++)//以j结尾 
		{
			if(i==1)
			{
				dp[i][j]=abs(num[i]-hash[j]);
				continue;
			}
			if(dp[i-1][j]<minn)
			{
				minn=dp[i-1][j];
			}
			dp[i][j]=minn+abs(num[i]-hash[j]);
		//	printf(\"%d \",dp[i][j]);
			
		}
	//	printf(\"\\n\");
	}
	
	int minn=inf;
	for(int i=1;i<=count;i++)
	{
		minn=min(minn,dp[n][i]);
	}
	printf(\"%d\\n\",minn);
	return 0;
} 

TLE代码如下：

/*
最优子结构：dp[i][j]第i个数以第j大的数作为结尾得到的非严格递增(递减)子序列的最小花费 
子问题:min((dp[i-1][k]|1<=k<=j))+num[i]-hash[j] hash[j]:第j大的数的值
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 2055
#define inf 1000000000
int dp[maxn][maxn]; 
int hash[maxn];
int num[maxn];
int temp1[maxn];
int main()
{
	int n;
	scanf(\"%d\",&n);
	for(int i=1;i<=n;i++)
	{
		scanf(\"%d\",&num[i]);
		temp1[i]=num[i];
	} 
	sort(temp1+1,temp1+1+n);
	int count=2;
	hash[1]=temp1[1];
	for(int i=2;i<=n;i++)
	{
		if(temp1[i]!=temp1[i-1])
			hash[count++]=temp1[i];//把temp[i]映射成count 
	}
	count--;
	/*for(int i=1;i<=count;i++)
	{
		printf(\"%d->%d \",hash[i],i);
	}
	printf(\"\\n\");*/
	for(int i=1;i<=n;i++)//第i个数 
	{
		for(int j=1;j<=count;j++)//以j结尾 
		{
			if(i==1)
			{
				dp[i][j]=abs(num[i]-hash[j]);
				continue;
			}
			int minn=inf;
			for(int k=1;k<=j;k++)
			{
				minn=min(dp[i-1][k],minn);
			}
			dp[i][j]=minn+abs(num[i]-hash[j]);
		//	printf(\"%d \",dp[i][j]);
			
		}
	//	printf(\"\\n\");
	}
	
	int minn=inf;
	for(int i=1;i<=count;i++)
	{
		minn=min(minn,dp[n][i]);
	}
	printf(\"%d\\n\",minn);
	return 0;
}