Chopsticks

題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=234

題目大意：給定n個(gè)筷子的長度，取k+8套筷子，每套有3個(gè)，長度分別為A,B,C。要求k+8套筷子中(A-B)^2的和最小，輸出這個(gè)最小值。

分析：題目中筷子長度是非降序排列的，所以最小的兩個(gè)A和B一定是相鄰的。先不考慮筷子C，只要留著就行。

　　令dp[i][j]表示從 j 個(gè)筷子中取 i 套筷子的最優(yōu)值。

　　dp[i][j] = min {dp[i][j-1] , dp[i-1][j-1] | (n - j > 3*(k - i))剩下的筷子可以湊滿}

　　可以用滾動(dòng)數(shù)組

代碼如下：

1 # include<iostream> 2 # include<cstring> 3 # include<cstdio> 4 using namespace std; 5 long MAX = 2147483647; 6 long dp[1005][5005]; 7 long f[5005]; 8 int main(){ 9 int T,i,j,k,n; 10 long temp; 11 cin>>T; 12 while(T--) 13 { 14 scanf("%d%d",&k,&n); 15 for(i=1;i<=n;i++) 16 cin>>f[i]; 17 k += 8; 18 memset(dp,0,sizeof(dp)); 19 for(i=1;i<=k;i++) 20 { 21 for(j=i*2;j<=n;j++) 22 { 23 dp[i][j] = MAX; 24 if(j>i*2) 25 dp[i][j] = dp[i][j-1]; 26 if(n-j>(k-i)*3) 27 { 28 temp = dp[i-1][j-2] + (f[j]-f[j-1])*(f[j]-f[j-1]); 29 if(temp<dp[i][j]) 30 dp[i][j] = temp; 31 } 32 } 33 } 34 cout<<dp[k][n]<<endl; 35 } 36 return 0; 37 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/acm-bingzi/p/3258805.html

總結(jié)

以上是生活随笔為你收集整理的ZOJ 1234 Chopsticks（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。