本文主要是介绍UVA - 10271 Chopsticks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：从n个筷子中选出k+8对（x,y,z）使得总的(x-y)^2最小，切z最大，容易想出dp[i][j]表示前i个筷子中选j对使得权值最小，先确定最终的状态是我们用n个筷子选出k+8组使得权值最小，对于第i个筷子我们有选与不选的情况，当我们选的时候dp[i][j] = dp[i-1][j]，选的话那么就是一定要连着i-1这根一起选，所以dp[i][j] = dp[i-2][j-1]+权值，所以
dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+权值),接下来就是确定是先i开始循环，还是j，因为我们一定每次都要取更新最小值，所以我们将i放在外面，但问题来了，第三根怎么选呢，脑子短路了，看了学长的，只要逆着排序就好了，因为我们每次都选出最小的，只要i>=3*j的话，就一定能有第三根是最大的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 5010;
const int INF = 1<<29;int dp[MAXN][MAXN];
int arr[MAXN];int main(){int t;scanf("%d",&t);while (t--){int k,n;scanf("%d%d",&k,&n);k += 8;for (int i = n; i >= 1; i--)scanf("%d\n",&arr[i]);for (int i = 1; i <= n; i++){dp[i][0] = 0;for (int j = 1; j <= k; j++)dp[i][j] = INF;}for (int i =3; i <= n; i++)for (int j = 1; j <= k; j++)if (i >= j * 3 && dp[i-2][j-1] != INF)dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(arr[i]-arr[i-1])*(arr[i]-arr[i-1]));printf("%d\n",dp[n][k]);}return 0;
}这篇关于UVA - 10271 Chopsticks的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
