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("%d\n",dp[k][n]); 42 } 43 return 0; 44 } View Code

轉載于:https://www.cnblogs.com/fanminghui/p/3863889.html

總結

以上是生活随笔為你收集整理的hdu 1500 Chopsticks的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。