UVa 10154 - Weights and Measures

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

貌似又叫做烏龜塔。

Solution

作法可參考: LIS。

先將烏龜依可負荷重量(已排除自身)做排序。每次先選可負荷較少的，如果一樣則是看誰較輕，從上往下開始建烏龜塔。
利用 dp[] 來記錄到每層所需要負荷的重量。只要此烏龜可負荷其上面的重量，就可判斷是否較有潛力成為這層的烏龜(也就是比較輕的)。有點像 LIS 的作法，去更新每隻烏龜下面可接的烏龜。
最後只要從尾巴開始掃，看長度多少即可。

用單純數字來舉例的話(由小到大): dp[0] = 0

step    1  5  3  7  4  5
 0      x  x  x  x  x  x    init
 1      1  x  x  x  x  x    可接 1。
 2      1  5  x  x  x  x    5 可接在 1 後面。
 3      1  3  x  x  x  x    3 可接在 1 後面，且比 5 更有潛力
 4      1  3  7  x  x  x    7 可接在 1 後面，但不會比 3 更有潛力。7 還可接在 3 後面。
 5      1  3  4  x  x  x    4 可接在 3 後面，且比 7 更有潛力。(省略其他檢查)
 6      1  3  4  5  x  x    5 可接在 4 後面。

長度為 4: 1 3 4 5

step 表 看第幾個數字。

Code

UVa 10154UVa 10154 - Weights and Measures

#include<cstdio>
#include<algorithm>
#define N 5610
#define INF 1e9
using namespace std;
struct Turtle
{
    int w, p;
}turtle[N];

int main()
{
    int count = 1, w, p;
    while (scanf("%d%d", &w, &p) != EOF)
    {
        turtle[count].w = w;
        turtle[count].p = p - w;
        count++;
    }

    sort(turtle + 1, turtle + count, [](const Turtle& a, const Turtle& b)
    {
        if (a.p == b.p)
            return a.w < b.w;
        return a.p < b.p;
    });

    int dp[N] = { 0 }, i, k;
    for (i = 1; i < count; i++)
        dp[i] = INF;

    //dp[1]為最上層
    for (i = 1; i < count; i++)
        for (k = i; k; k--)//由上往下，因不能重複使用數字
            if (dp[k - 1] < turtle[i].p)
                dp[k] = min(dp[k], dp[k - 1] + turtle[i].w);

    int len = count - 1;
    while (dp[len] == INF)
        len--;
    printf("%d\n", len);

    return 0;
}