uva 10271 - Chopsticks

In China, people use a pair of chopsticks to get food on the table, but Mr. L is a bit different. He uses a set of three chopsticks -- one pair, plus an EXTRA long chopstick to get some big food by piercing it through the food. As you may guess, the length of the two shorter chopsticks should be as close as possible, but the length of the extra one is not important, as long as it's the longest. To make things clearer, for the set of chopsticks with lengths A,B,C(A<=B<=C), (A-B)² is called the 'badness' of the set.

It's December 2nd, Mr.L's birthday! He invited K people to join his birthday party, and would like to introduce his way of using chopsticks. So, he should prepare K+8 sets of chopsticks(for himself, his wife, his little son, little daughter, his mother, father, mother-in-law, father-in-law, and K other guests). But Mr.L suddenly discovered that his chopsticks are of quite different lengths! He should find a way of composing the K+8 sets, so that the total badness of all the sets is minimized.

Input

The first line in the input contains a single integer T, indicating the number of test cases(1<=T<=20). Each test case begins with two integers K, N(0<=K<=1000, 3K+24<=N<=5000), the number of guests and the number of chopsticks. There are N positive integers L_i on the next line in non-decreasing order indicating the lengths of the chopsticks.(1<=L_i<=32000).

Output

For each test case in the input, print a line containing the minimal total badness of all the sets.

Sample Input

Sample Output

Note

个人觉得这是一道好题，这题一开始没有思路，被筷子中的最长那根和输入按递增顺序所迷惑了，后来看了网上的题解，恍然大悟！

首先，筷子应该按照从大到小排序，因此需要倒序输入。然后用一个类似前缀和的数组来维护相邻两项的差的平方。

为什么要从大到小排序，这是有原因的。首先可以肯定，短的筷子一定是相邻的，否则无论是哪种情况，只要兑换一下筷子组合，就能得到更优解，这个留给你们自己去证明吧。

dp[i][j]表示前i根筷子，组成了j个筷子组合。开始决策第i根筷子，它可以组成1个筷子组合，那么根据前面的结论，必然是和第i-1根筷子组合了，但是一定要保证i>=3*j,因为去掉这些短筷，还必须有j根长筷，否则不符合题意；当然第i根筷子不组成1个筷子组合，那么前i-1根组成了j个组合，必须注意此时i-1>=3*j，理由同上。

到这里有没有发现降序排列的好处？只有降序排列，最后第i根筷子才能安稳地与第i-1根筷子组合，因为长筷都出现在i之前了，但是换成递增顺序呢？第i根筷子就不一定能与第i-1根筷子组合，这要看第i根筷子后面还有多少筷子，因为这些要用来做长筷的，比如i-2，i-3组成一双短筷，i-1，i组成一双短筷，那么显然还差i+1和i+2来做这两对的长筷，这样问题就复杂多了，还要记录差了多少长筷，用三维数组，我觉得也不见得好推理，更何况复杂度不允许！那么按照降序排列，前i根除了组合外剩余的筷子均可用来做长筷，只要保证上面的两个不等式即可，问题一下子简单了很多。

最后就是初始化问题了，dp[i][0]=0,其余为inf。

代码：

#include<cstdio>
#include<iostream>
using namespace std;

int a[5010],dp[5010][1010];
const int inf=1<<30;
int main()
{
    int t,k,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&k,&n);
        k+=8;
        for(int i=n;i>0;i--)
            scanf("%d",a+i);
        for(int i=n;i>1;i--)
            a[i]=(a[i]-a[i-1])*(a[i]-a[i-1]);
        for(int i=1;i<=n;i++){
            dp[i][0]=0;
            for(int j=1;j<=k;j++)
                dp[i][j]=inf;
        }
        for(int i=3;i<=n;i++)
            for(int j=1;j<=k;j++){
                if(i>=3*j)
                    dp[i][j]=min(dp[i][j],dp[i-2][j-1]+a[i]);
                if(i>=3*j+1)
                    dp[i][j]=min(dp[i][j],dp[i-1][j]);
            }
        printf("%dn",dp[n][k]);
    }
	return 0;
}

dp[j][i]=min{dp[j][i-1],dp[j-1][i-2]+a[i]},看到了吗？j层只取决于j层和j-1层，因此一个倒推，一个顺推，注意边界条件，那两个不等式还是存在的。

初始化dp[i]=0了，倒推时直接赋值了，顺推取小。详见代码。

代码：

#include<cstdio>
#include<iostream>
using namespace std;

int a[5010],dp[5010];
const int inf=1<<30;
int main()
{
    int t,k,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&k,&n);
        k+=8;
        for(int i=n;i>0;i--)
            scanf("%d",a+i);
        for(int i=n;i>1;i--)
            a[i]=(a[i]-a[i-1])*(a[i]-a[i-1]);
        for(int i=1;i<=n;i++)
            dp[i]=0;
        for(int j=1;j<=k;j++){
            int m=j*3;
            for(int i=n;i>=m;i--)
                dp[i]=dp[i-2]+a[i];
            for(int i=m+1;i<=n;i++)
                dp[i]=min(dp[i],dp[i-1]);
        }
        printf("%dn",dp[n]);
    }
	return 0;
}

最后

以上就是腼腆芹菜为你收集整理的uva 10271 - Chopsticks的全部内容，希望文章能够帮你解决uva 10271 - Chopsticks所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。