uva 10271 Chopsticks

本文主要是介绍uva 10271 Chopsticks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有t组测试数据，要你选出n+8对三元组（从m个数中）。要求这三个数x<=y<=z,其中代价为(x-y)^2。问最小的代价是多少。
设map[i][j]是从前j个数中选出i对三元组的最小的代价。
可以有如下的状态转移方程：
map[i][j]=min(map[i][j-1],map[i-1][j-2]+bad[j]);

问题是z如何安排，当我们把数从大到小去排，然后加上限制条件i*3<=j的时候，就可以消除z的影响。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=5005;
int len[N],bad[N];
int map[1020][N];
int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);n+=8;for(int i=1;i<=m;i++) scanf("%d",&len[m+1-i]);for(int i=1;i<=m;i++) bad[i]=(len[i]-len[i-1])*(len[i]-len[i-1]);memset(map,0x7f,sizeof(map));for(int i=0;i<=m;i++) map[0][i]=0;for(int i=1;i<=n;i++){for(int j=3*i;j<=m-(n-i)*2;j++){map[i][j]=min(map[i][j-1],map[i-1][j-2]+bad[j]);}}printf("%d\n",map[n][m]);}
}

这篇关于uva 10271 Chopsticks的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---