Chopsticks UVA - 10271

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

#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();
}
}

最后

以上就是冷静猫咪为你收集整理的Chopsticks UVA - 10271的全部内容，希望文章能够帮你解决Chopsticks UVA - 10271所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。