https://www.acwing.com/problem/content/514/
想到的一种解法是，每隔x个高度抽点出来。
比如从j高度开始。
判断j+x高度时：
dp[i][j]+1
判断j+2x高度时：
dp[i][j+x]+1,dp[i][j]+2
可以看到后面的这个是一起+1的，所以最小值也是和新加的项取min，然后+1就可以了。
每个点只会被更新一次，复杂度O(nm)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n, m, k;
int dp[2][1005];
pair<int, int> L[10005], R[10005];
int X[10005], Y[10005];
void update1(int i, int p, int x, int y) {
//更新初始位置为p，步长为x的点，保证0<p<=x
//printf("p=%d, x=%d, y=%d\n",p,x,y);
i = i & 1;
if(p + y <= m)
dp[i][p] = min(dp[i][p], dp[!i][p + y]);
int curmin = dp[!i][p] + 1;
for(int q = p + x;; q += x) {
if(q <= m){
if(q+y<=m)
dp[i][q] = min(dp[i][q], dp[!i][q + y]);
dp[i][q] = min(dp[i][q], curmin);
}
else {
dp[i][m] = min(dp[i][m], curmin);
break;
}
curmin = min(curmin, dp[!i][q]) + 1;
}
//要在另一个函数把碰到管道的置为INF
/*for(int p = 1; p <= n; ++p) {
printf("dp[%d][%d]=%d\n", i, p, dp[i & 1][p]);
}
printf("\n");*/
}
int curp = 1;
void update2(int i) {
//把碰到管道的置为INF
int ci = i & 1;
if(curp <= k && L[curp].first == i) {
for(int p = 1; p <= L[curp].second; ++p)
dp[ci][p] = INF;
for(int p = R[curp].second; p <= m; ++p)
dp[ci][p] = INF;
for(int p = 1; p <= m; ++p)
if(dp[ci][p] < INF / 2) {
++curp;
return;
}
printf("%d\n%d\n", 0, curp - 1);
exit(0);
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d%d%d", &n, &m, &k);
memset(dp[0], 0, sizeof(dp[0]));
dp[0][0] = INF;
for(int i = 0; i < n; ++i) {
scanf("%d%d", &X[i], &Y[i]);
}
for(int i = 1; i <= k; ++i) {
scanf("%d%d%d", &L[i].first, &L[i].second, &R[i].second);
R[i].first = L[i].first;
}
sort(L + 1, L + 1 + k);
sort(R + 1, R + 1 + k);
for(int i = 1; i <= n; ++i) {
//printf("i=%d\n", i);
memset(dp[i & 1], INF, sizeof(dp[i & 1]));
for(int p = 1; p <= X[i-1]; ++p)
update1(i, p, X[i-1], Y[i-1]);
/*for(int p = 1; p <= n; ++p) {
printf("dp[%d][%d]=%d\n", i, p, dp[i & 1][p]);
}
printf("\n");*/
update2(i);
/*for(int p = 1; p <= n; ++p) {
printf("dp[%d][%d]=%d\n", i, p, dp[i & 1][p]);
}
printf("\n");*/
}
int ans = INF;
for(int p = 1; p <= m; ++p)
ans = min(ans, dp[n & 1][p]);
printf("%d\n%d\n", 1, ans);
return 0;
}