題意：有n只筷子，然后選出來k+8套（一套有三只，分別ABC），一套筷子質量為最小的兩只的平方，選出的使得總的質量和最小。

思路：01背包。dp[i][j]表示j套利選出來i套的最優解，每個都有選當前和不選當前兩中狀態。

code：

#include <bits/stdc++.h> using namespace std;typedef long long ll; typedef unsigned long long ull; typedef long double ld;const int INF=0x3fffffff; const int inf=-INF; const int N=1000000; const int M=6005; const int mod=1000000007; const double pi=acos(-1.0);#define cls(x,c) memset(x,c,sizeof(x)) #define cpy(x,a) memcpy(x,a,sizeof(a)) #define ft(i,s,n) for (int i=s;i<=n;i++) #define frt(i,s,t) for (int i=s;i>=t;i--) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lrt rt<<1 #define rrt rt<<1|1 #define middle int m=(r+l)>>1 #define lowbit(x) (x&-x) #define pii pair<int,int> #define mk make_pair #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout);int n,k,T; int v[M],dp[M][M]; int main() {scanf("%d",&T);ft(ca,1,T){scanf("%d %d",&k,&n);k+=8;frt(i,n-1,0) scanf("%d",&v[i]);ft(i,1,k) ft(j,0,n){dp[i][j]=0;if (i*3>j){dp[i][j]=9999999;continue;}dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(v[j-1]-v[j-2])*(v[j-1]-v[j-2]));}printf("%d\n",dp[k][n]);} }

總結

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

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