uva 10271——Chopsticks-蒲公英云

uva 10271——Chopsticks

题意：有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]);
    }
}