分析

我们可以先定义状态 为在第 列，第 行所需要的最小点击次数。那么我们有如下转移 这个是如果选择点击的转移。 这个是不点的转移。那么我们通过滚动数组的技巧，第一种的转移优化到 。然后对于 的时候特判一下就好了。时间复杂度为 。对于障碍物我们直接赋值 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;} 
const int N = 21000,inf = 0x3f3f3f3f;
struct Node {
    int p,l,h;
}h[N];
int up[N],dw[N],n,m,K,f[N][1100],vis[N];
int main() {
    n = read();m = read();K = read();
    for(int i = 1;i <= n;i++) up[i] = read(),dw[i] = read();
    for(int i = 1;i <= K;i++) {
        h[i].p = read() + 1;h[i].l = read();h[i].h = read();
        vis[h[i].p] = i;
    }
    memset(f,0x3f,sizeof(f));
    for(int i = 1;i <= m;i++) f[1][i] = 0;
    for(int i = 2;i <= n + 1;i++) {
        for(int j = up[i - 1] + 1;j <= m;j++) f[i][j] = min(f[i][j],min(f[i-1][j - up[i - 1]],f[i][j - up[i - 1]]) + 1);
        for(int j = m - up[i - 1];j <= m;j++) f[i][m] = min(f[i][m],min(f[i-1][j],f[i][j]) + 1);
        for(int j = 1;j <= m - dw[i - 1];j++) f[i][j] = min(f[i][j],f[i-1][j + dw[i - 1]]);
        if(vis[i]) {
            for(int j = 1;j <= h[vis[i]].l;j++) f[i][j] = inf;
            for(int j = h[vis[i]].h;j <= m;j++) f[i][j] = inf;
        }
        int res = inf;
        for(int j = 1;j <= m;j++) res = min(f[i][j],res);
        if(res == inf) {
            cout << "0" << endl;int ans = 0;
            for(int j = 1;j < i;j++) ans += !!vis[j];
            cout << ans << endl;
            return 0; 
        }
    }
    int ans = inf;
    for(int i = 1;i <= m;i++) ans = min(ans,f[n + 1][i]);
    cout << "1\n" << ans << endl;
    return 0;
}