首页 > ACM题库 > HDU-杭电 > HDU 4205-Parking Ships[解题报告]HOJ
2015
05-23

HDU 4205-Parking Ships[解题报告]HOJ

Parking Ships

问题描述 :

Life on the great oceans has been good for captain Blackbeard and his fellow pirates. They have gathered so many treasures, that each of them is able to buy a house on their favorite island. The houses on this island are all placed in a long row along the beach line of the island. Next to a house, every pirate is also able to buy his own ship to do their own bit of plundering. However, this causes a whole new kind of problem.
Along the beach line there is a long pier where every pirate can park his ship. Although there is enough space along the pier for all the ships, not every pirate will be able to park in front of his house. A pirate is happy with his parking space if some part of the parking space is in front of the center of his house. Captain Blackbeard has been given the diffcult task of assigning the parking spaces to the pirates. A parking space for a pirate i is a range [ai, bi] (ai, bi∈R) along the pier such that li<= bi – ai, where li is the length of the ship of pirate i. Thus, pirate i is happy if ai <= xi <= bi, where xi is the center of the house of pirate i. Clearly, parking spaces of different pirates must be interior disjoint (the ends of ranges can coincide).
Above all, the captain wants a good parking space for himself, so he gives himself the parking space such that the center of his ship is aligned with the center of his house. Next to that, he wants to make as many pirates happy as possible. Can you help him out?

输入:

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with one integer n (1 <= n <= 1,000): the number of pirates including the captain.
2.n lines with on each line two integers xi (-10^9 <= xi <= 10^9) and li (1 <= li <= 10^9): the center of the house of the ith pirate and the total length of his ship, respectively. The first pirate in the input is always the captain.

输出:

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with one integer n (1 <= n <= 1,000): the number of pirates including the captain.
2.n lines with on each line two integers xi (-10^9 <= xi <= 10^9) and li (1 <= li <= 10^9): the center of the house of the ith pirate and the total length of his ship, respectively. The first pirate in the input is always the captain.

样例输入:

2
5
0 6
-5 2
-4 1
4 2
5 3
4
0 4
-5 4
3 4
5 3

样例输出:

5
3

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 1000 + 10;
int DP[MAX_SIZE][MAX_SIZE];
const int INF = 0x3fffffff;

struct tNode
{
    int x, len;
}Node[MAX_SIZE];

bool comp(const tNode &a, const tNode &b)
{
    return a.x < b.x;
}

int getMax(int a, int b)
{
    return a < b ? b : a;
}
int getMin(int a, int b)
{
    return a < b ? a : b;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d", &Node[i].x, &Node[i].len);
        }
        int captain = Node[0].x;
        sort(Node, Node + n, comp);
        for(int i = 0; i < n; ++i)
        {
            if(captain == Node[i].x)
            {
                captain = i;
                break;
            }
        }
        for(int i = 0; i < captain; ++i)
            DP[i][0] = -INF;
        for(int i = n - 1; i > captain; --i)
            DP[i][0] = INF;
        DP[0][1] = Node[0].x;
        DP[0][2] = INF;
        for(int i = 1; i < captain; ++i)
        {
            for(int j = 1; j <= i + 1; ++j)
            {
                DP[i][j] = DP[i - 1][j];
                if(DP[i - 1][j - 1] <= Node[i].x)
                {
                    DP[i][j] = getMin(DP[i][j], getMax(DP[i - 1][j - 1] + Node[i].len, Node[i].x));
                }
                else
                    DP[i][j] = INF;
            }
            DP[i][i + 2] = INF;
        }
        DP[n - 1][1] = Node[n - 1].x;
        DP[n - 1][2] = -INF;
        for(int i = n - 2; i > captain; --i)
        {
            for(int j = 1; j <= n - i; ++j)
            {
                DP[i][j] = DP[i + 1][j];
                if(DP[i + 1][j - 1] >= Node[i].x)
                    DP[i][j] = getMax(DP[i][j], getMin(DP[i + 1][j - 1] - Node[i].len, Node[i].x));
                else
                    DP[i][j] = -INF;
            }
            DP[i][n - i + 1] = -INF;
        }
        int left = static_cast<double>(Node[captain].x) - static_cast<double>(Node[captain].len) / 2;
        int right = static_cast<double>(Node[captain].x) + static_cast<double>(Node[captain].len) / 2;
        if(Node[captain].len % 2 != 0)
            right++;

        int lmax = 0, rmax = 0;
        for(int j = captain; j >= 0; --j)
        {
            if(DP[captain - 1][j] <= left)
            {
                lmax = j;
                break;
            }
        }
        for(int j = n - captain - 1; j >= 0; --j)
        {
            if(DP[captain + 1][j] >= right)
            {
                rmax = j;
                break;
            }
        }
        printf("%d\n", 1 + lmax + rmax);
    }
    return 0;
}