解題區►解題區 - UVa

UVa 11052 - Economic phone calls

contents

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

Problem

給一台手機的通話紀錄，通話紀錄分成兩類，其中一類標記為 + 表示重要訊息，另一類標記為 - 表示不重要訊息。手機中的歷史紀錄時間不會紀錄年份，靠著有順序的嚴格遞增表示同一年。

假使現在只想要知道 + 的所有電話紀錄發現在哪一年份，可以忽略部分的 - 來推估每一通電話的年份，請問最少要保留幾份紀錄。

每一組的最後一筆測資表示現在年份。

Sample Input

1
2
3
4
5
6
7
8
9
7
12:31:23:59 0123456789012345 +
07:21:19:00 1337 -
01:01:00:00 0987654321 -
07:21:14:00 1337 -
11:11:11:11 11111111111 +
01:01:00:00 0123456789 +
01:01:00:00 0987654321 -
0

Sample Output

1
6

Solution

可以推測，從現在到最早期的 + 紀錄之間的每一年至少需要一通電話。

首先將輸入的每一通電話算出年份，然後找到需要回溯的最早期電話，在這更之前的電話紀錄就可以無視，推算時間與更早期的紀錄無關。

定義 dp[i] 表示第 i 筆電話紀錄後，能夠使得 [i, n] 之間 + 紀錄回溯年代的最少紀錄筆數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
	int n;
	int time[1024];
	char mark[1024][4];
	while (scanf("%d", &n) == 1 && n) {
		int mm, dd, HH, MM;
		for (int i = 0; i < n; i++) {
			scanf("%d:%d:%d:%d %*s %s", &mm, &dd, &HH, &MM, mark[i]);
			time[i] = ((mm * 31 + dd) * 24 + HH) * 60 + MM;
		}
		int year[1024] = {}, cur_year;
		for (int i = 1; i < n; i++) {
			if (time[i] <= time[i-1])
				year[i] = year[i-1] + 1;
			else
				year[i] = year[i-1];
			cur_year = year[i];
		}
		int dp[1024] = {}, last = -1, trace = -1;
		// dp[i] : record i satisfy that all `+` record can trace in year[i]~cur_year
		for (int i = n - 1; i >= 0; i--) {
			if (last == -1 && year[i] == cur_year)
				dp[i] = 1; 		// record now time.
			else
				dp[i] = n - i; 	// record all after this. (init value)
			if (last == -1 && (mark[i][0] == '+' || year[i] != cur_year))
				last = i;
			if (mark[i][0] == '+')
				trace = i;
		}
		for (int i = last; i >= trace; i--) {
			for (int j = i + 1; j < n; j++) {
				if (year[i] == year[j])
					dp[i] = min(dp[i], dp[j] + 1);
				else if (time[i] >= time[j] && year[j] - year[i] == 1)
					dp[i] = min(dp[i], dp[j] + 1);
				else
					break;
				if (mark[j][0] == '+')	break;
			}
		}
//		for (int i = 0; i < n; i++)
//			printf("[%d] y %d dp %d\n", i, year[i], dp[i]);
//		printf("%d %d\n", last, trace);
		printf("%d\n", dp[trace]);
	}
	return 0;
}