hdu 1500 Chopsticks

57 阅读 0 评论 38 点赞

我是靠谱客的博主耍酷毛衣，最近开发中收集的这篇文章主要介绍hdu 1500 Chopsticks，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://acm.hdu.edu.cn/showproblem.php?pid=1500

dp[i][j]为第i个人第j个筷子。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5
 6 int dp[1011][5011];
 7 int a[5011];
 8 int k,n;
 9 int sqr(int x)
10 {
11
return x*x;
12 }
13 bool cmp(const int a,const int b)
14 {
15
return a>b;
16 }
17
18 int main()
19 {
20
int t;
21
scanf("%d",&t);
22
while(t--)
23 
{
24
scanf("%d%d",&k,&n);
25
memset(dp,0,sizeof(dp));
26
memset(a,0,sizeof(a));
27
for(int i=1; i<=n; i++)
28 
{
29
scanf("%d",&a[i]);
30 
}
31
sort(a+1,a+n+1,cmp);
32
k=k+8;
33
for(int i=1; i<=k; i++)
34 
{
35
dp[i][i*3]=dp[i-1][i*3-2]+sqr(a[i*3-1]-a[i*3]);
36
for(int j=i*3+1; j<=n; j++)
37 
{
38
dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+sqr(a[j-1]-a[j]));
39 
}
40 
}
41
printf("%dn",dp[k][n]);
42 
}
43
return 0;
44 }