【動态規劃】[NOIP2014] codevs3729飛揚的小鳥

去年這題炸了，然後一年過去了，我又寫炸了

人老了，寫不動代碼了……

雖然複雜度是O(NM)沒錯，但是常數越寫越大簡直快要飛起來了 = =

其實感覺可以開個輔助數組會降不少常數……

題目點這裡

dp[i][j]表示到達(i, j)這個位置需要的最小點選次數

三個轉移：

向上點選不到頂：step[i][j] = min(step[i][j], step[i - 1][j - x[i]] + 1, step[i][j - x[i]] + 1) 

向上點到頂：step[i][M] = min(step[i][M], step[i - 1][j] + 1, step[i][j] + 1)

這兩個轉移用到了完全背包一樣的優化，就是點選多次的時候直接從上一次點選的轉移。要注意的是需要用到的位置可能是不可到的（即上一次點選到的位置非法但多點一次就合法了），是以要每個位置都轉移然後再把非法位置清空了（當然這個工作開一個輔助數組就行了 orz）。

不點選向下掉：step[i][j] = min(step[i][j], step[i - 1][j + y[i]])

最後對于非法情況的處理我成功地把整個圖重掃了一遍。沒辦法，我執杖

另外，還是覺得《To the moon》真好聽啊><

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int inf = 0x3f3f3f3f;

int N, M, K;
int x[10005], y[10005], pre[10005], cnt[10005];
int ban[10005][1005];
int step[10005][1005];

inline void update(int &a, int b, int c = inf) {
    if (b > c) b = c; if (a > b) a = b;
}

int main()
{
    ios :: sync_with_stdio(false);
    
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++ i) cin >> x[i + 1] >> y[i + 1];
    while (K --) {
        int P, L, H; cin >> P >> L >> H;
        ++ P; ++ pre[P];
        for (int i = 1; i <= L; ++ i) ban[P][i] = 1;
        for (int i = H; i <= M; ++ i) ban[P][i] = 1;
    }
    for (int i = 1; i <= N; ++ i) pre[i] += pre[i - 1];
    
    memset(step, inf, sizeof(step));
    for (int i = 1; i <= M; ++ i) if (!ban[1][i]) step[1][i] = 0;
    for (int i = 2; i <= N + 1; ++ i) {
        for (int j = x[i] + 1; j < M; ++ j) update(step[i][j], step[i - 1][j - x[i]] + 1, step[i][j - x[i]] + 1);
        for (int j = M - x[i]; j <= M; ++ j) update(step[i][M], step[i - 1][j] + 1, step[i][j] + 1);
        for (int j = 1; j <= M; ++ j) if (ban[i][j]) step[i][j] = inf;
        for (int j = 1; j <= M - y[i]; ++ j) if (!ban[i][j]) update(step[i][j], step[i - 1][j + y[i]]);
    }
    
    int ans = inf;
    for (int i = 1; i <= M; ++ i) update(ans, step[N + 1][i]);
    if (ans ^ inf) cout << "1" << endl << ans << endl;
    else {
        for (ans = 1; ans <= N; ) {
            bool flag = 0;
            for (int j = 1; j <= M; ++ j)
                if (step[ans][j] ^ inf) { flag = 1; break; }
            if (flag) ++ ans; else break;
        }
        cout << "0" << endl << pre[ans - 1] << endl;
    }
    return 0;
}