首页 > 搜索 > DFS搜索 > HDU 3928-Catch the Thief-DFS-[解题报告]HOJ
2015
04-14

HDU 3928-Catch the Thief-DFS-[解题报告]HOJ

Catch the Thief

问题描述 :

A thief stole a big diamond in a party. The diamond was in the door of the house. So everyone can tell if there is a diamond when he enter and exit the house.

The cop think that the thief must be one of the guests. So they have got the timetable of the entrance time and exit time of everyone. They are arranging how to ask them to know who is the thief. When ask somebody, the cop could know if the diamond was still being there when they entering and exiting.

Of course, thief will tell lie. To simplify the problem, the thief will always tell you that the diamond was there. To simplify the problem, we assume that the thief stole the diamond when he exit.

The cop want to ask as few people as possible. Please help them to find the minimum number of guests they have to ask.

输入:

The first line contains a single positive integer T( T <= 100 ), indicates the number of test cases.
For each test case: First line contains an integer N(1<=N<=25), indicates the number of Guests
The Timetable of the party – 2N numbers, 1-N each one twice, the first appearance means he enter. the second appearance means he exit.

输出:

The first line contains a single positive integer T( T <= 100 ), indicates the number of test cases.
For each test case: First line contains an integer N(1<=N<=25), indicates the number of Guests
The Timetable of the party – 2N numbers, 1-N each one twice, the first appearance means he enter. the second appearance means he exit.

样例输入:

4
1
1 1
2
1 1 2 2
4
1 1 2 2 3 3 4 4
5
1 4 4 2 5 5 3 3 2 1

样例输出:

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 2

Hint
Case 1: Only one guest there. So the thief must be him Case 2: The data shows the timetable as below: in time 1, #1 enter the house; in time 2, #1 exit the house; in time 3, #2 enter the house; in time 4, #2 exit the house; The cop will only ask #2. If he answer YES/YES, the thief must be him; If he answer NO/NO, the thief must be #1. Case 3: There's a solution which cop only ask 2 times: The cop will ask #3 first, If he answer YES/YES, the thief may be #3 or #4, then ask #4 to know who is the thief; If he answer NO/NO, the thief may be #1 or #2. then ask #2 to know who is the thief; he can't answer YES/NO or NO/YES.


题目大意:在一个Party上, 一个贼偷了1颗钻石并装成了guests,已知每个人进入和离开这个party的时间,一警察每次问一个人进入party和离开party的时候那颗钻石是否还在那里,已知如果问的是那个贼,他总会告诉你钻石还在,而且钻石是在贼离开的时候被偷走的。问这个警察最少要问多少次才能确定哪个是贼

题目分析:
1.假如已知钻石是在时间[x, y]之间被偷的,而且这段时间中有且只有一个人离开,那么那个人必定是贼
2.设贼是在t 时刻偷走钻石的
对于每个人,假设他的进出时间为[a, b]它的回答可能会有3钟情况(yes表示钻石尚存,no表示钻石已经不在)
    (1)进入是yes,离开时yes(后用yes/yes简写),则t 一定在[b, 2*n]
    (2)yes/no: 则t 一定在[a+1, b-1]
    (3)no/no: 则t 一定在[1, a-1]
至于no/yes的情况是不可能出现的,因为贼都会告诉你yes的
3.如果一个人的回答告诉你t 时刻在 [a, b],如果a > b 或者在时间段[a, b]里面根本没有人离开,显然这个状态是不合法的
4.假设现在已知t 时刻是在[a, b], 如果一个人的回答可能会告诉你t 时刻是在[a, b]的,则这家伙就没必要问他了
OK,有了以上YY的理论分析,我们可以设状态f(x, y)表示要知道那个在时间[x, y]之间偷走了钻石的贼是谁所需要询问人的最小次数
状态转移方程:
f(x, y) = min(max{ f(ri[i], y) + 1,  f(max(le[i]+1, x), min(ri[i-1]+1, y))+1,  f(x, le[i]-1)+`1
}

);

最后求f(2, 2*n)便是答案
AC CODE:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#define Maxn 100
#define inf 1<<30
using namespace std;
int T, n, f[Maxn][Maxn], out[Maxn][Maxn];
int le[Maxn], ri[Maxn];
int dfs(int x, int y)
{
     if (f[x][y] != -1) return f[x][y];
     if (out[x][y] == 1) return f[x][y] = 0;
     
     int t1, t2, t3, tmp = inf;
     for (int i=1; i<=n; i++)
     {
         t1 = t2 = t3 = -inf;
         int x1 = x, yy1 = min(le[i]-1, y);   // no/no 
         if (yy1 == y) continue;
         if (x1 <= yy1 && out[x1][yy1]) t1 = dfs(x1, yy1);
         
         int x2 = max(le[i]+1, x), y2 = min(ri[i]-1, y);  //  yes/no
         if (x2 == x && y2 == y) continue;     
         if (x2 <= y2 && out[x2][y2]) t2 = dfs(x2, y2);
          
         int x3 = max(ri[i], x), y3 = y;     //  yes/yes
         if (x3 == x) continue;         
         if (x3 <= y3 && out[x3][y3]) t3 = dfs(x3, y3); 
         
         tmp = min(tmp, max(t1,max(t2, t3)));         
     }
     return f[x][y] = tmp + 1;
     }
int main()
{
    int k;
    scanf(“%d”, &T);
    for (int t=1; t<=T; t++)
    {
        memset(le, -1, sizeof(le));
        memset(f, -1, sizeof(f));
        memset(out, 0, sizeof(out));
        
        scanf(“%d”, &n);
        for (int i=1; i<=2*n; i++)
        {
            scanf(“%d”, &k);  
            if (le[k] == -1) le[k] = i;
            else ri[k] = i; 
        }
        
        for (int i=1; i<=2*n; i++)
          for (int j=i; j<=2*n; j++)
            for (int p=1; p<=n; p++)
            if (ri[p] <= j && ri[p] >= i) out[i][j]++;
        
        printf(“Case #%d: %d\n”, t, dfs(2, 2*n));
    }
    
    return 0;
    }

参考:http://blog.163.com/hacker_james/blog/static/659024432011711115116906/


,
  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯