HDU -- 免费馅饼(ACM Step: 3.2.8)

一、概述

1、问题描述

在一个长度为10的数轴中，从0到10编号，gameboy站在坐标为5的点，此刻时间为0。

已知，每过1秒，在不同的坐标点都有可能出现馅饼，并且gameboy每秒钟只能走1个数轴单位的距离，求在已知馅饼掉落的时间和位置下gameboy可以得到的最多馅饼数，在每个位置可能同时出现多个馅饼。

2、问题链接

HDU -- 免费馅饼(ACM Step: 3.2.8)

3、问题截图

HDU -- 免费馅饼(ACM Step: 3.2.8)

图1.1 问题截图

二、算法思路

此题和数塔问题类似。

假设t表示当前的时间，即t=0，p表示当前的位置，即p=5。

在t=1时，gameboy可以走到p=4、5、6这三个位置，他要走到哪个呢？他应该走到可以得到最大值的位置，因此需要继续分析，4、5、6哪个才能得到最大值。现在问题变成了找到t=1时，p=4、5、6这三个位置的最大值中的较大者。

对于4，要求它的最大值，需要在t=2时，从p=3、4、5三个位置中找出最大值，然后加上它自己所带有的馅饼数。

对于5，要在t=2时，从p=4，5，6中的最大值，并且加上自己的馅饼数。

6也是一样。

可以发现，最后几乎要求在所有可能的t，以及所有可能的位置p，中可以得到的最大值问题。

由于最后一层可以得到的最大值就是它们本身的馅饼数，因此可以从最下层往上构造，这样同时可以保证对每个子问题只求过一次。

也可以使用递归，假设问题求在（t=0，p=5）的最大值，那么它可以转变为（1，4），（1，5），（1，6）三个字问题，即可以使用3次递归。

要求解（1，4），即求解（2，3），（2，4），（2，5）

要求解（1，5），即求解（2，4），（2，5），（2，6）

要求解（1，6），即求解（2，5），（2，6），（2，7）

可以发现用递归会使得同一个子问题如（2，5）要被计算多次，所以使用从下向上的解法将避免这个问题。

三、算法实现

#include <cstdio>    // for printf, scanf
#include <array>

using std::array;

const int COORDINATE_NUMS = 11;
const int MAXSIZE = 1e5;
array<array<int, COORDINATE_NUMS>, MAXSIZE> data;    // input 2d-array, data[i][j] indicating whether time i and position j have input
array<array<int, COORDINATE_NUMS>, MAXSIZE> ans;    // ans for answer, result 2d-array that assume gameboy begin at time i and position j

int input(int);    // for input data
int calculate(int);    // for calculate result
void print(int);    // for print result

int main()
{
    int n;

    while (1){
        scanf("%d", &n);
        if (n == 0)
            break;

        n = input(n);
        n = calculate(n);
        print(n);

        // clear array for next input
        data = array<array<int, COORDINATE_NUMS>, MAXSIZE>();
        ans = array<array<int, COORDINATE_NUMS>, MAXSIZE>();
    }
    return 0;
}
// get max value of 2 integer
int get_2_max(int a, int b)
{
    return (a>b)?a:b;
}

// get max value of 3 integer
int get_3_max(int a, int b, int c)
{
    int ret = a;

    if(b > ret)
        ret = b;

    if(c > ret)
        ret = c;

    return ret;
}
// read input data, return the depth of digit tower
int input(int n)
{
    int x, t;
    int ret = 0;

    for (int i=0; i<n; ++i){
        scanf("%d%d", &x, &t);

        ++data[t][x];

        if (t > ret)
            ret = t;
    }
    return ret;
}

// calculate the result, T indicate the max value of input time
int calculate(int T)
{
    int t = T;    // t indicate array index of the current time

    // max vale of the last time of position i is itself
    for (int i=0; i<COORDINATE_NUMS; ++i)
        ans[t][i] = data[t][i];

    --t;    // done with time t, t indicate to prior time now

    for (int i=t; i>=0; --i){
        // the max value of position 0 and 10 of time i depend on positon 0, 1 and 9, 10 of time i+1, respectively
        ans[i][0] = get_2_max(ans[i+1][0], ans[i+1][1]) + data[i][0];
        ans[i][10] = get_2_max(ans[i+1][9], ans[i+1][10]) + data[i][10];

        // other positons depends on three value of time i+1
        for (int j=1; j<COORDINATE_NUMS-1; ++j)
            ans[i][j] = get_3_max(ans[i+1][j-1], ans[i+1][j], ans[i+1][j+1]) + data[i][j];
    }
    return ans[0][5];
}

// print the result
void print(int n)
{
    printf("%d\n", n);
}

HDU -- 免费馅饼(ACM Step: 3.2.8)

相关推荐