UVa 12245 - Hyperactive Girl

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

可用工作區間為 [1, m]，則要求分配 [li, ri] 的方式，找到所有可能的分配集合符合

• 所有區間完全覆蓋住 [1, m] (區間可以重疊)
• 每一個區間至少單獨佔有一個時間點

Sample Input

9 9
2 7
3 5
6 8
5 6
2 8
2 6
0 2
7 9
2 8

18 9
8 15
1 17
0 10
9 18
12 15
1 5
5 6
0 10
11 17

8 7
0 3
2 5
5 8
1 3
3 6
4 6
0 2
1 1
0 1
2 1
0 1
0 0

Sample Output

4
2
4
1
0

Solution

可以得知每一個區間一定會被前一個區間覆蓋到一些，所以為了保證增加的下一個區間不會影響到前一個區間的”單獨佔有的時間點”消失，紀錄狀態為 [前一個區間, 當前區間] 進行轉移方程。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;

struct Interval {
    int l, r;
    bool operator<(const Interval &a) const {
        return l < a.l || (l == a.l && r < a.r);
    }
};
int main() {
    int n, m;
    const int mod = 100000000;
    Interval D[128];
    while(scanf("%d %d", &m, &n) == 2 && n+m) {
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &D[i].l, &D[i].r);
        }
        sort(D, D+n);
        int dp[128][128] = {}; // [prev][now]
        int ret = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = (D[i].l == 0);
            for (int j = i+1; j < n; j++) {
                if (D[j].l > D[i].l && D[j].r > D[i].r && D[j].l <= D[i].r) {
                    for (int k = 0; k <= i; k++) {
                        if (D[k].r >= D[j].l && k != i)
                            continue;
                        dp[i][j] = (dp[i][j] + dp[k][i])%mod;
                    }
                }
            }
            if (D[i].r == m) {
                for (int j = 0; j <= i; j++)
                    ret = (ret + dp[j][i])%mod;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}