UVA_10271

??? 總的來講，我們應(yīng)該從大到小去安排筷子，因為如果從小到大去安排的話，最后剩下的不一定可以作為最長的那根。

??? 我首先將筷子反過來存在了數(shù)組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])}，當(dāng)然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;
}

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的UVA 10271 Chopsticks的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。