【題解】HDU 1257 最少拦截系统

【題目敘述】https://vjudge.net/problem/HDU-1257
【解題想法】DP + Greedy

  • vector <int> missile:紀錄每個已經部署的攔截系統還可以攔截的飛彈高度。
  • 每次對付一枚新的飛彈,就先從已經部署的攔截系統中,找出戰力最弱,但還足以對付的攔截系統,優先使用。這樣不會浪費戰力,可以部署最少的攔截系統。記得更新使用過的攔截系統的戰力(攔截高度)。
  • 如果已經部署的所有攔截系統,都沒有能力對付新的飛彈,則增加一組新的攔截系統。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, x;
    while (cin >> N){
        vector<int> missile;
        int i = 0;
        while (N--) {
            cin >> x;
            for (i=0; i<missile.size(); i++){
                if (x <= missile[i]){
                    missile[i] = x;
                    break;
                }
            }
            if (i == missile.size()){
                missile.push_back(x);
            }
            sort(missile.begin(), missile.end());
        }
        cout << missile.size() << '\n';
    }
    return 0;
}
分享本文 Share with friends