Uva11052 - Economic phone calls

題目大意

你的手機上有通話紀錄，格式為
MM:DD:hh:mm phone-number +/-
其中 + 為重要的訊息，- 為不重要的訊息
並且訊息的年份能夠從訊息的時間推得(嚴格遞增為一年)
我們要在可以推的所有重要訊息年份的前提下，選擇刪掉最多的不重要訊息
並且在最後輸出留下來的訊息數
(最下面一條是最近的訊息)

重點觀念

分析

• 先把訊息的年份找出來
• 初始化每則訊息的的最小訊息數
  • 在最近的這一年
    • 只要在重要的訊息後出現的就只需要自己一則訊息就可以辨識年份
    • 在重要訊息後則先定為 n - i
  • 在其他年
    • 先大致定為 n - i
  • 順便找 last 與最舊的重要訊息
    • last 是在最近一年最新的重要訊息或是換年後的最新的訊息
• 用 dp 找出到目前的所選擇的訊息前面需要多少訊息才能辨識年份
  • 在找最小訊息數時只要時間比前面的少且年份只差一年，則中間的訊息可以忽略
  • 如果同一年也可以忽略
  • 最後找最舊得重要訊息辨識年份所需要的訊息則數即是答案

程式題目碼

#include <iostream>

using namespace std;

int main() {
    int n;

    while (cin >> n && n != 0) {
        int timestamp[n];
        bool isImportant[n];
        int year[n];

        for (int i = 0; i < n; i++) {
            int month, day, hour, minute;
            char mark;

            scanf("%d:%d:%d:%d %*s %c", &month, &day, &hour, &minute, &mark);
            timestamp[i] = ((((month * 31) + day) * 24) + hour) * 60 + minute;
            isImportant[i] = mark == '+';
        }

        year[0] = 0;
        int current_year;

        for (int i = 1; i < n; i++) {
            if (timestamp[i] <= timestamp[i - 1]) {
                year[i] = year[i - 1] + 1;
            } else {
                year[i] = year[i - 1];
            }
            current_year = year[i];
        }

        int dp[n], last = -1, first_important = -1;

        for (int i = n - 1; i >= 0; i--) {
            if (last == -1 && year[i] == current_year) {
                dp[i] = 1;
            } else {
                dp[i] = n - i;
            }

            if (last == -1 && (isImportant[i] || year[i] != current_year)) {
                last = i;
            }

            if (isImportant[i]) {
                first_important = i;
            }
        }

        for (int i = last; i >= first_important; i--) {
            for (int j = i + 1; j < n; j++) {
                if (year[i] == year[j] || (timestamp[i] >= timestamp[j] && year[j] - year[i] == 1)) {
                    dp[i] = min(dp[i], dp[j] + 1);
                } else {
                    break;
                }

                if (isImportant[j]) {
                    break;
                }
            }
        }

        cout << dp[first_important] << endl;
    }

    return 0;
}