uva10271

74 阅读 0 评论 49 点赞

我是靠谱客的博主坚强中心，这篇文章主要介绍uva10271，现在分享给大家，希望可以做个参考。

题目大意：
有一个人需要用三根筷子，其中两根短的长度距离越近越好，长的只要比他们两个都长就可以了，badness = 两根短的长度相减的平方
这个人想在生日会上教朋友们这种方法，有k个朋友n根筷子。
还有包括他在内的八个亲人。
需要3 * (k + 8)根筷子，问最小的badness是多少。
思路：
将筷子从大到小排序。
dp[i][j]表示的是前i根筷子前j个人最少的badness是多少。
那么就要考虑第i跟筷子选不选给第j个人，如果选的话就是dp[ i -2][j - 1] + (c[i] - c[i - 1])的平方(因为选了第i根筷子的话就要选第i - 1根筷子)，如果不选的话，那么就是dp[i -1][j]。
代码：

复制代码

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
29
30
31
32
33
#include <iostream>
using namespace std;
#include <cstring>
#include <stdio.h>

int c[5005];
int dp[5005][1005];
const int INF = 0x3f3f3f3f;
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n,k;
        scanf("%d %d",&k,&n);
        k = k + 8;
        for(int i = n; i > 0; i--)
            scanf("%d",&c[i]);
        for(int i = 1; i <= n; i++) {
            dp[i][0] = 0;
            for(int j = 1; j <= n; j++){
                dp[i][j] = INF;
            }
        }
        for(int i = 3;i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                if(i >= j * 3 && dp[i - 2][j - 1] != INF)
                    dp[i][j] = min(dp[i - 1][j],dp[i - 2][j - 1] + (c[i] - c[i - 1])*(c[i] - c[i - 1]));
            }
        }
        printf("%dn",dp[n][k]);
    }
    return 0;
}