2014-07-28

UVa 11766 - Racing Car Computer

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
6. Solution

Problem

The racing cars of today are equipped with so many sophisticated equipment. Introduction of a new visual transducer which is interfaced with the on-board computer can tell you on the fly how many cars are ahead of you while how many are trailing. There are N cars on a racing track. Each has an on-board computer with the new feature. During the race, every single car’s computer keeps displaying two integers, a (The number of cars in front of him) & b (The number of cars behind him) for a particular moment. It is possible that at some time, some of the cars are racing side by side i.e. they are exactly at the same location. A car will not consider any other car at the same location to be a leading or trailing car.

Now, it is suspected that some of the new transducers are not working properly inside such high speed vehicles. The report with all computers’ data generated at a particular timestamp is reported to you. You are to determine the minimum number of cars that have faulty data.

Input

Each test case begins with an integer N (1<=N<=1000), the number of cars on a track . The next N lines each has two integers - a & b (0<=a,b<=1500) for a particular car.

The last test case is followed by a line with a single 0 indicating the end of input.

Output

For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the minimum number of cars that must have faulty data according to the report.

Sample Input

Output for Sample Input

1 2	Case 1: 3 Case 2: 1

Solution

題目描述：

有n个人进行比赛，给出每个人的状况，a表示这个人前面有a个人，b表示说这个人后面有b个人。问说最少有多少个人的状态是不成立的。

題目解法：

將問題轉換成區間，來表示這個人可能所在的區間，假使前面有 a 個人，後面有 b 個人，則這個人可能所在為 [a+1, n-b]，我們允許區間內最高容量為 n - b - a (當作權重) 個人，求不相交區間的最大權重。

最後 n 扣除這個最大權重就是答案。

#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n, cases = 0;
    int a, b;
    while(scanf("%d", &n) == 1 && n) {
        map<int, int> R[1024];
        for(int i = 0; i < n; i++) {
            scanf("%d %d", &a, &b);
            if(a + b >= n)
                continue;
            int &ww = R[a+1][n-b];
            ww = min(ww + 1, n - a - b);
        }
        int ret = 0, dp[1024] = {};
        for(int i = 0; i <= n; i++) {
            if(i)
                dp[i] = max(dp[i], dp[i-1]);
            for(map<int, int>::iterator it = R[i+1].begin();
                it != R[i+1].end(); it++)
                dp[it->first] = max(dp[it->first], dp[i] + it->second);
            ret = max(ret, dp[i]);
        }
        printf("Case %d: %d\n", ++cases, n - ret);
    }
    return 0;
}

Morris' Blog