UVa11052 - Economic phone calls(動態規劃 Dynamic programming )

題目大意

我有一台很老的手機，他的 RAM 並不大，最近我們遇上了 RAM 用滿的問題，我們現在必須刪除一些電話紀錄，但有一些規則要遵守

• 最後一次電話紀錄一定是今年的紀錄
• 格式為 mm:dd:HH:MM phone +\-，前面為時間，電話名稱，是否為重要紀錄
• 我們只能夠刪除非重要紀錄
• 手機並不會記錄年份，因此我們判斷年份是使用相對時間，也就是如果前一筆的時間 < 下一筆的時間，我們可以定義這兩筆資料在同年份；如果前一筆的時間 >= 下一筆的時間 我們則定義這兩筆資料的年份不一樣，前一筆的資料年份比較遠、後一筆資料年份比較近。
• 我們可以透過上一點來判斷年份，也就是每年至少都要用一筆資料。

請告訴我們最少需要保存幾個資料，就可以將重要資料全部保存並且可以判斷每通紀錄的年份。

題目連結

重點觀念

• 動態規劃的時機 (當資料並不能延續狀態，而是會需要前面資料輔助時就用動態規劃)
• 了解時間可以用字串比較

分析

這題是我認為算是非常麻煩的問題，我學習他花了將近 4 小時。

由於我們要保存最少的資料，但完整性、一樣能辨識年份，我們主要會遇到一些困難點

• 找出最後一年的重要紀錄，如果沒有就直接隨便找一筆紀錄
• 假如兩筆重要紀錄分別是 2001, 2003 年，那我們要留下 2002 的一筆不重要紀錄
• 舉例如下，那我們是不是這三筆資料都必須留下，否則年份辨識不正確

  01:10:11 1234 + 
  01:02:23 2345 -
  01:12:11 3456 +

• 所有的重要紀錄都必須被留下

根據這些困難點，會發現如果我們使用 greedy 會很難寫，因為例如第三點的情況，我們的 greedy 就必須根據過去資料去判斷，如果第一筆資料與第二筆資料中間又塞入很多的非重要紀錄那就更麻煩了。

因此這邊我們就使用可以提取過去資料與當前資料判斷的動態規劃。

主要的動態規劃則是

• dp[i] 保留至第 i 個紀錄中最少要保存幾個紀錄
• 在重要紀錄中的那些不重要紀錄我只紀錄一筆，dp[i] = min(dp[i], dp[j]+1、i < j < n，j 表示同年份的資料，如果直接提取 dp[j]+1，+1 則是紀錄 i
• 如果碰到重要紀錄，則直接跳出 for j 迴圈，因為重要紀錄不可省略

主要架構如上述所說，如果有些不清楚則建議查看下方題目程式碼

參考連結

Uva11052 - Economic phone calls by txya900619

心得

這題好難QQQ，而且好複雜！ 我原本是想要用 greedy 去做，做到一半才發現第三點用 greedy 去做並不好做。

但是也沒有想到 dp 要怎麼做比較好，就看力瑋的程式碼，不斷思考怎麼運作，後來詢問力瑋程式碼意思才逐漸開竅。

能想出這份程式碼的人真的太聰明了，我的缺點是遇到太多大問題時不擅長拆解，但我擅長將小問題解決，可能跟我的個性有關吧，喜歡注重細節，但常常忽略大局。

總之，中庸之道我也需要攝取攝取。
但我想要成為一位優秀的人，住在漂亮的房子、給小孩好的教育，幸福的人生。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 1020;
int n, dp[MAXN];

struct record{ //用於記錄每筆資訊
    string time, phone, mark;
    int year;

    //constructor 
    record(string _time, string _phone, string _mark, int _year){
        time = _time;
        phone = _phone;
        mark = _mark;
        year = _year;
    };
    record(): time(""), phone(""), mark(""), year(0){} //一開 year 始預設為 0

};
deque<record> info; //用於紀錄題目每筆紀錄

void debug(){ //debug 無意義
    for(int i = 0; i < n; i++){
        cout << info[i].time << ' ' << info[i].phone << ' ' << info[i].mark << ' ' << info[i].year << '\n';
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> n && n){ //輸入資料
        string time, phone, mark;
        info.clear(); //清空，避免影響到其他測資
        for(int i = 0; i < n; i++){ //輸入資料
            cin >> time >> phone >> mark;
            info.push_back( record(time, phone, mark, 0));
        }

        int year = 0; //先對題目的資料做辨識年份
        for(int i = 1; i < n; i++){
            if(info[i].time <= info[i-1].time) info[i].year = ++year; //年份不同， year 因此加一
            else info[i].year = year;
        }

        //debug();

        //first_mark 為年份最久的重要記錄，因為在遠的紀錄我們不須留下
        // flag 判斷是否已經讀取到年份最新的重要紀錄
        //last_mark 年份最新的重要紀錄
        int first_mark = n, flag = 1, last_mark;
        for(int i = n-1; i >= 0; i--){
            if(info[i].mark == "+") first_mark = i; //最後一次讀取就是年份最久的重要紀錄

            //我們必須把最新的年份直到出現今年的重要紀錄時都讓 dp[i] = 1，
            //因為這些紀錄，我們只需要紀錄一筆即可
            dp[i] = flag && info[i].year == year ? 1 : n-i; 
            if(flag && (info[i].mark == "+" || info[i].year != year)){ //更新最近紀錄
                flag = 0;
                last_mark = i;
            }

        }

        //dp 動態規劃，由最近年份至最遠年份
        for(int i = last_mark; i >= first_mark; i--){
            for(int j = i+1; j < n; j++){ //不斷的往最近年份推
                //由於我們動態規劃的核心是想要做成 重要紀錄、一筆非重要紀錄、重要紀錄
                //重要紀錄、非重要紀錄，視為一個區塊

                //但中間的一筆非重要紀錄，不一定只有一筆，所以我們就透過下方 if 來 dp
                //我們選擇*哪一個*非重要紀錄可以讓我們的 dp[i] 最小，下方的 dp[j] 則是上一個區塊，我們從上一個區塊中哪一個 dp[j] 可以使 dp[i] 最小

                //如果年份相同 or (前一年的資料，但離第 i 份資料不差超過一年)
                if(info[i].year == info[j].year || \
                   (info[i].year + 1 == info[j].year && info[i].time >= info[j].time))
                    //判斷 dp[i] 的資料是否比較少 or 省略 j~i 的紀錄，直接 dp[j]+1 誰少
                    dp[i] = min(dp[i], dp[j]+1); 
                else break; //當前區塊結束，跳出迴圈，原因是並非同區塊的資料

                if(info[j].mark == "+") break; //當前區塊結束，跳出迴圈，原因是遇到重要紀錄
            }
        }

        //for(int i = 0; i < n; i++) cout << dp[i] << ' ';
        //cout << '\n';
        cout << dp[first_mark] << '\n'; //輸出保留至第一個紀錄中最少要保存幾個紀錄
    }


    return 0;
}