UVA - 10271 Chopsticks 线性DP

问题

在N个数字中挑选K组，每组3个数字，A<=B<=C，要求${\sum }_i(A_i-B_i{)}^2$最小

分析

除了最长的筷子，其他两只短的一定是相邻的
dp[i][j]，前i只筷子分给j个人的最小代价
状态转移方程：
$i<3\ast j，dp[i][j]=INF$
$i>=3\ast j$, 第i个筷子分给j的代价 $dp[i-2][j]+(len[i-1]-len[i])\ast (len[i-1]-len[i])，不分给j的代价dp[i-1][j]$，所以
$dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(len[i-1]-len[i])\ast (len[i-1]-len[i]))$

#include<iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxk=1020,maxc=5005,maxp=55,INF=0x3f3f3f3f;
int T,k,n,len[maxc],dp[maxc][maxk]; //dp[i][j]，前i只筷子分给j个人的最小代价
//除了最长的筷子，其他两只短的一定是相邻的
int main(void){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&k,&n);
        k+=8;
        for(int i=n;i>0;--i){
            scanf("%d",&len[i]);  //逆序排列，从大到小
        }
        for(int i=1;i<=n;++i){
            for(int j=k;j>=1;--j){
                if(i<3*j) dp[i][j]=INF;
                else break;
            }
        }

        for(int i=1;i<=n;++i){
            for(int j=1;j<=k;++j){
                //保持足够的筷子分配
                if(i>=3*j){
                    //第i个筷子不分给j dp[i-1][j]，分给了j  dp[i-2][j]+(len[i-1]-len[i])*(len[i-1]-len[i])
                    dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(len[i-1]-len[i])*(len[i-1]-len[i]));
                }
            }
        }
        printf("%d\n",dp[n][k]);
    }
    return 0;
}