UVA 10271 Chopsticks

UVA_10271

    总的来讲，我们应该从大到小去安排筷子，因为如果从小到大去安排的话，最后剩下的不一定可以作为最长的那根。

    我首先将筷子反过来存在了数组a[]里面，这样用f[i][j]表示一共有到第i根这么多的筷子安排给j个人的最小的badness，那么如果3*j==i+1，f[i][j]=f[i-2][j-1]+(a[i–1]–a[i])*(a[i-1]-a[i])，否则f[i][j]=min{f[i][j-1],f[i-2][j-1]+ (a[i–1]–a[i])*(a[i-1]-a[i])}，当然3*j<=i+1且j<=K+8。

#include<stdio.h>
#include<string.h>
#define MAXD 5010
#define MAXK 1010
#define INF 1000000000
int K, N, a[MAXD], f[MAXD][MAXK];
void init()
{
    int i, j;
    scanf("%d%d", &K, &N);
    for(i = N - 1; i >= 0; i --)
        scanf("%d", &a[i]);
}
void solve()
{
    int i, j, k, temp;
    for(i = 0; i < N; i ++)
        for(j = 0; j <= K + 8; j ++)
        {
            if(j)
                f[i][j] = INF;
            else
                f[i][j] = 0;
        }
    for(i = 0; i < N; i ++)
        for(j = 1; 3 * j <= i + 1 && j <= K + 8; j ++)
        {
            f[i][j] = f[i - 2][j - 1] + (a[i - 1] - a[i]) * (a[i - 1] - a[i]);
            if(3 * j < i + 1)
            {
                if(f[i - 1][j] < f[i][j])
                    f[i][j] = f[i - 1][j];
            }
        }
    printf("%d\n", f[N - 1][K + 8]);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        init();
        solve();
    }
    return 0;
}