Uva-10271 Chopsticks(DP)

122 阅读 0 评论 81 点赞

我是靠谱客的博主典雅耳机，这篇文章主要介绍Uva-10271 Chopsticks(DP)，现在分享给大家，希望可以做个参考。

题意:佳佳的一套筷子有三只，两根短筷子和一只比较长的.如果一套筷子的长度分别为a,b,c,(a <= b <= c),那么这套筷子的质量就为(a-b)^2.现在佳佳有n(n <= 1000)只筷子,他希望找到一种方法搭配好K+8套筷子,使得这些筷子的质量和最小.

分析:把所有筷子从小到大排序后,设f[i][j]表示当前已经凑齐了j套筷子,并且最后一套筷子中最小的那根为i的最小质量和,如果3*j > n-i+1那么当前状态一定不合法,有个这个状态我们发现只要处理下上个阶段的后缀最小值就能实现O(1)转移了.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define N 10005
#define INF 1047483647
#define MOD 1000000007
using namespace std;
int T,K,n,ans,a[5005],f[5005][1010],suc[5005][1010];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(f,0x3f,sizeof(f));
        memset(suc,0x3f,sizeof(f));
        scanf("%d%d",&K,&n);
        for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        for(int i = 0;i <= n;i++) suc[i][0] = 0;
        for(int j = 1;j <= K+8;j++)
         for(int i = n-2;i >= 1;i--)
         {
            if((n-i+1) >= 3*j)
             f[i][j] = abs(a[i] - a[i+1])*abs(a[i] - a[i+1]) + suc[i+2][j-1];
            suc[i][j] = min(suc[i+1][j],f[i][j]);
         }
        cout<<suc[1][K+8]<<endl;
    }
}