Chopsticks UVA - 10271

90 阅读 0 评论 60 点赞

我是靠谱客的博主冷静猫咪，这篇文章主要介绍Chopsticks UVA - 10271，现在分享给大家，希望可以做个参考。

类似于背包问题的一道动态规划的题目，同时要注意，在选取三根筷子作为结果的时候，要将最小的两根用来计算结果，题目当中给出的数据是从小到大的，所以我们要进行逆序读入，也就是保证读入的数据是从大到小的，这样便于后面动态规划的操作。因为后面动态规划的过程都是两个地选取与前面的某一个进行组合。接着是开始进行动态规划的过程，仿照背包问题的做法和空间优化的方法，因为我们需要的集合个数为K，首先从1开始进行动态规划，假设当前要组合的集合个数为m，每次选取两个点与前面中的某一个点进行组合，同时计算新加入的集合的代价与前m-1个集合代价之和，逐步推进到最后，然后对后续的代价进行更新，保存最小的代价的值即可，具体实现见如下代码：

复制代码

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
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<deque>
using namespace std;
class Solve{
public:
int K, N;
int value[5010];
int dp[5010];
int assit[5010];
void Init(){
for (int i = N; i >=1 ; i--)
cin >> value[i];
for (int i = 2; i <= N; i++)
assit[i] = (value[i] - value[i - 1])*(value[i] - value[i - 1]);
}
void Deal(){
Init();
memset(dp,0,sizeof(dp));
for (int i = 1; i <= K; i++){
int amount = 3 * i;
for (int j = N; j >= amount; j--){
dp[j] = dp[j - 2] + assit[j];
}
for (int j = amount + 1; j <= N; j++)
if (dp[j - 1] < dp[j]) dp[j] = dp[j - 1];
}
cout << dp[N] << endl;
}
};
int main(){
int T;
cin >> T;
Solve a;
while (T--){
cin >> a.K >> a.N;
a.K += 8;
a.Deal();
}
}