这道题题目很坑。
首先可以码出一个n三方的dp。（码的好有85分）
#include<cstdio> #include<queue> using namespace std; const int N = 10002, M = 1002, limit = (1 << 30) - 1; int n, m, k, dp[N][M], x[N], y[N]; bool f[N][M]; priority_queue <int, vector <int>, greater <int> > q; void read(int &x) { x = 0; char s = getchar(); while(s > '9' || s < '0') s = getchar(); while(s <= '9' && s >= '0') { x = (x << 1) + (x << 3) + s - '0'; s = getchar(); } } int Min(const int x, const int y) { if(x < y) return x; return y; } int main() { int a, b, c, tmp, ans; bool flag, flagg; read(n); read(m); read(k); for(int i = 1; i <= n; i ++) { read(x[i]); read(y[i]); } for(int i = 1; i <= k; i ++) { read(a); read(b); read(c); q.push(a); for(int j = 1; j <= b; j ++) f[a][j] = 1; for(int j = c; j <= m; j ++) f[a][j] = 1; } for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) dp[i][j] = limit; for(int i = 1; i <= n; i ++) { flagg = 0; for(int j = 1; j <= m; j ++) { flag = 0; if(f[i][j]) continue; if(j + y[i] <= m && dp[i - 1][j + y[i]] != limit) { flag = 1; dp[i][j] = dp[i - 1][j + y[i]]; } if(j == m && dp[i - 1][m] != limit) { flag = 1; dp[i][j] = Min(dp[i][j], dp[i - 1][m] + 1); } if(j == m) { for(int u = 1; u < m; u ++) if(dp[i - 1][u] != limit) { flag = 1; dp[i][j] = Min(dp[i][j], dp[i - 1][u] + ((m - u) % x[i] == 0 ? (m - u) / x[i] : (m - u) / x[i] + 1)); } } for(int u = 1; j - u * x[i] >= 1; u ++) if(dp[i - 1][j - u * x[i]] != limit) { flag = 1; dp[i][j] = Min(dp[i][j], dp[i - 1][j - u * x[i]] + u); } if(flag) flagg = 1; } if(! flagg) { tmp = i; break; } } if(flagg) { ans = limit; for(int i = 1; i <= m; i ++) ans = Min(dp[n][i], ans); printf("1\n%d\n", ans); } else { ans = 0; while(! q.empty()) { if(q.top() < tmp) { ans ++; q.pop(); } else break; } printf("0\n%d\n", ans); } return 0; }接下来我们就想要优化u的部分。观察的出，这其实就是完全背包！至于为什么用2维而不是1维，我们看到第2维要从上和从下两个方向拓展。
#include<cstdio> #include<queue> #include<iostream> using namespace std; const int N = 10002, M = 2002, limit = (1 << 30) - 1; int n, m, k, dp[N][M], x[N], y[N], down[N], up[N]; priority_queue <int, vector <int>, greater <int> > q; void read(int &x) { x = 0; char s = getchar(); while(s > '9' || s < '0') s = getchar(); while(s <= '9' && s >= '0') { x = (x << 1) + (x << 3) + s - '0'; s = getchar(); } } int main() { int a, tmp, ans, maxx = 0; bool flag; read(n); read(m); read(k); for(int i = 1; i <= n; i ++) { read(x[i]); read(y[i]); down[i] = 0; up[i] = m + 1; maxx = max(maxx, x[i]); } for(int i = 1; i <= k; i ++) { read(a); read(down[a]); read(up[a]); q.push(a); } for(int i = 1; i <= n; i ++) for(int j = 1; j <= maxx + m; j ++) dp[i][j] = limit; for(int i = 1; i <= m; i ++) dp[0][i] = 0; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) dp[i][j + x[i]] = min(dp[i][j] + 1, min(dp[i][j + x[i]], dp[i - 1][j] + 1)); for(int j = m + 1; j <= m + x[i]; j ++) dp[i][m] = min(dp[i][m], dp[i][j]);//先越界处理，再给m for(int j = 1; j <= m - y[i]; j ++) dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i]]); for(int j = 1; j <= down[i]; j ++) dp[i][j] = limit;//可能被更新，但这样不对 for(int j = up[i]; j <= m; j ++) dp[i][j] = limit; flag = 0; for(int j = 1; j <= m; j ++) if(dp[i][j] != limit) { flag = 1; break; } if(! flag) { tmp = i; break; } } if(flag) { ans = limit; for(int i = 1; i <= m; i ++) ans = min(dp[n][i], ans); printf("1\n%d\n", ans); } else { ans = 0; while(! q.empty()) { if(q.top() < tmp) { ans ++; q.pop(); } else break; } printf("0\n%d\n", ans); } return 0; }注意，数组要开m的两倍！
