UVA Chopsticks(10271)

124 阅读 0 评论 82 点赞

我是靠谱客的博主典雅小蚂蚁，这篇文章主要介绍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 与之相匹配。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}