NOIP 2014飞扬的小鸟(DP优化)

考场的70分暴力（实际只有50分因为数组开小了……）

考场代码（数组大小已修改）

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <functional>

 using namespace std;

 #define rep(i, a, b)    for (int i(a); i <= (b); ++i)

 #define dec(i, a, b)    for (int i(a); i >= (b); --i)

 #define LL        long long

 #define fi        first

 #define se        second

 const int INF =     <<    ;

 const int N =     +    ;

 const int M =     +    ;

 int dp[M][N], x[N], y[N], u[N], d[N];

 int n, m, q, ans, xn, ln, rn, _max, pos;

 bool c[N];

 int main(){

     scanf("%d %d %d ", &n, &m, &q);

     rep(i, , n - ) scanf("%d %d ", x + i, y + i);

     rep(i, , n) u[i] = m, d[i] = ;

     memset(c, false, sizeof c);

     rep(i, , q){

         scanf("%d %d %d ", &xn, &ln, &rn);

         c[xn] = true;

         u[xn] = rn - ;

         d[xn] = ln + ;

     }

     //rep(i, 0, n) printf("%d %d\n", d[i], u[i]);

     memset(dp, 0xff70, sizeof dp);_max = dp[][];

     rep(i, , m) dp[][i] = ;

     rep(i, , n - ){

         rep(j, d[i], u[i]){

             if (dp[i][j] >= _max) continue;

             int k = j - y[i];

             if (k >=  && k <= m) dp[i + ][k] = min(dp[i + ][k], dp[i][j]);

             k = j;int num = ;

             while (true){

                 k += x[i]; ++num;

                 if (k > m) k = m;

                 if (k >=  && k <= m) dp[i + ][k] = min(dp[i + ][k], dp[i][j] + num);

                 if (k == m) break;

             }

         }

     }

     ans = _max;

     rep(i, , m) ans = min(ans, dp[n][i]);

     if (ans < _max){

         printf("%d\n%d\n", , ans);return ;

     }

     bool flag = false;

     ans = ;

     dec(i, n, ) {rep(j, , m)  if (dp[i][j] < _max) { pos = i - ;flag = true; break;} if (flag) break;}

     dec(i, pos, ) if (c[i]) ++ans;

     printf("%d\n%d\n", , ans);

     return ;

 }

然后回过来想正解。

其实我们把很多时间都浪费在这里了：

     while (true){

         k += x[i]; ++num;

         if (k > m) k = m;

         if (k >=  && k <= m) dp[i + ][k] = min(dp[i + ][k], dp[i][j] + num);

         if (k == m) break;

     }

其实这一步可以转过来直接利用完全背包的性质优化一下。转移只要O（1）就可以了。

这道题细节还是很多的，比较容易写挂。

正解：

 #include <bits/stdc++.h>

 using namespace std;

 #define rep(i, a, b)    for (int i(a); i <= (b); ++i)

 #define dec(i, a, b)    for (int i(a); i >= (b); --i)

 const int INF =     <<    ;

 const int N =     +    ;

 const int M =     +    ;

 int dp[N][M], x[N], y[N], u[N], d[N];

 int n, m, q, ans, xn, ln, rn, _max, pos;

 bool c[N];

 int main(){

     scanf("%d %d %d ", &n, &m, &q);

     u[n] = m + ; d[n] = ;

     rep(i, , n - ) scanf("%d %d ", x + i, y + i), u[i] = m + , d[i] = ;

     rep(i, , q){

         scanf("%d %d %d ", &xn, &ln, &rn);

         u[xn] = rn;

         d[xn] = ln;

     }

     rep(i, , n + ) rep(j, , m + ) dp[i][j] = INF;

     rep(i, , m) dp[][i] = ;

     rep(i, , n){

         rep(j, x[i - ], m){

             dp[i][j] = min(dp[i][j], dp[i - ][j - x[i - ]] + );

             dp[i][j] = min(dp[i][j], dp[i][j - x[i - ]] + );

         }

         rep(j, m - x[i - ], m){

             dp[i][m] = min(dp[i][m], dp[i - ][j] + );

             dp[i][m] = min(dp[i][m], dp[i][j] + );

         }

         rep(j, d[i] + , u[i] - ){

             if (j + y[i - ] <= m) dp[i][j] = min(dp[i][j], dp[i - ][j + y[i - ]]);

         }

         rep(j, , d[i]) dp[i][j] = INF;

         rep(j, u[i], m) dp[i][j] = INF;

     }

     ans = INF;

     rep(i, , m) ans = min(ans, dp[n][i]);

     if (ans != INF) return , printf("%d\n%d\n", , ans);

     int t = q;

     dec(i, n, ){

         rep(j, , m) ans = min(ans, dp[i][j]);

         if (ans != INF) break;

         if (u[i] != m + ) --t;

     }

     printf("%d\n%d\n", , t);

     return ;

 }