[线性结构DP][经典] UVA10271 Chopsticks

https://cn.vjudge.net/problem/UVA-10271

确实是经典。。。这种一开始没有什么头绪的dp，可以自己写出来几组样例，从中发掘最优解的性质，从而找到入手点。经过这样的一个xjb试探之后发现了：最优解的每组筷子中的短的那两根必定是在有序序列中相邻的。这样的话就可以确定一个转移的方法了，类似于背包里对于每个物品选还是不选，在这里对于每根筷子确定选还是不选，如果选，根据上面的性质他必须和之前的那根筷子组成一副。由此可以确定一个最基本的转移方程形式dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(len[i]-len[i-1])^2)，dp[i][j]表示对于前i个筷子分给j个人的最优解。这里还有一个问题是必须要给每个人再分一根最长的筷子，其实可以发现这个条件更好处理，只要满足i>=3*j就可以了：因为这个最长的筷子其实只要比另外俩长就可以，所以在最优解中的这根筷子有些人之间甚至可以换着用，顺序也无所谓，满足这个条件一定能分配好的。

对于这个状态转移方程，可以确定一个边界条件是dp[i][0]=0（从转移方程的第二部分可以得出来）

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int maxn = 5e3 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int chops[maxn];
bool cmp(int a,int b){return a>b;}
int dp[maxn][1005];

int main()
{
    int t,k,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&k,&n);k+=8;memset(dp,INF,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d",&chops[i]);
        sort(chops+1,chops+1+n,cmp);
        for (int i=1;i<=n;i++)
            dp[i][0]=0;
        for(int i=1;i<=n;i++)
            for (int j=1;j<=k&&3*j<=i;j++)
                dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(int)pow(chops[i]-chops[i-1],2));
        cout<<dp[n][k]<<endl;
    }
    return 0;
}