UVA Chopsticks(10271)

题目大意：

       有N个数，每个数表示筷子的长度，要你选出n+8组三元组，即n+8组筷子，每组3支筷子，要求这三支筷子的长度满足x<=y<=z，其中代价为(x-y)^2。问最小的代价是多少。

 

解题思路：

       动态规划问题，令dp[i][j] 表示从前 j 个数中选出 i 组三元组所需要的代价，则状态转方程为：

                                  dp[i][j] = min( dp[i][j-1], dp[i-1][j-2] + badness[j] );

其中badness[j] 表示选择第 j 个数和第 j-1 个数所需要的代价，需要在动态规划前预先计算出来。根据上述方程，例子如下：

       比如有数据1 8 10 16 19 22， 则dp[1][6] = min( dp[1][5] , dp[0][4] + (22 - 19)^2 )。前6个数取出1组数等于前5个数取出1组数和前4个数取出0组数（即取19 和 22）加上选取最后两个数所需的代价之间的最小的一个。

      由于要选取3数，且其中有一个数Z为最大者，若按照上述例子进行计算，不能保证选取的三个数中的Z是最大的，有可能是最小的，所以需要把数据进行倒序，即22 19 16 10 8 1，这样只要让 j >= i * 3，那么选取出来的每组数x 和 y，必然有一个Z 满足 z >= y >= x， 因为每次选取的 x 和 y 的开销一定是最小的，那么必然有一个比x和y大的数不会被选取，这样就必然有一个比x和y大的数 z 与之相匹配。

 

代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int badness[5010];
int dp[5010][5010];

int main()
{
	int T, K, N, temp;

	cin>>T;

	while( T-- )
	{
		cin>>K>>N;
		memset( badness, 0, sizeof(badness) );		
		memset( dp, 0x7f, sizeof(dp) );
		
		vector<int> v(N+1);
		for( int i = 1; i <= N; i++ )
		{
			cin>>temp;
			v[N-i+1] = temp;  //进行倒序存储
		}

		for( int i = 1; i <= N; i++ )
		{
			badness[i] = (v[i] - v[i-1]) * (v[i] - v[i-1]);
		}

		for( int i = 0; i < 5010; i++ )
			dp[0][i] = 0;
		for( int i = 1; i <= K+8; i++ )
		{
			int j;
			for( j = i*3; j <= N; j++ )
			{
				dp[i][j] = min( dp[i][j-1], dp[i-1][j-2] + badness[j] );
			}
		}

		cout<<dp[K+8][N]<<endl;
	}
	return 0;
}