题目传送门

题目分析

关于这道题，其实从题目中可以多点几次这个信息，可以很容易联想到完全背包，而且数据规模可以容许使用动态规划。
我们可以令$f[i][j]$表示到第$i$列$j$行最少需要点击屏幕的次数。
对于一个点$(i,j)$可以从$i-1$列的$(i-1,j-up[i-1])$、$(i-1,j+down[i-1])$转移过来。
同时根据完全背包，我们也可以从$(i,j-up[i-1])$转移，但要注意的是，即使是当前行的管道位置，我们也必须将其更新，因为它可能会对同一列的上方的位置产生影响，否则会影响同一列点击屏幕多次的状态。
同时，如果我们要用同一列的点来更新它的话，那么另一个点一定是从前一列的点向上跳得到，否则不能用来表示多次点击屏幕累计效果。
对于一列的最高点，我们要将它特殊处理，因为他可以是碰到顶部无法上升而得到，所以要对它进行多次更新。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# include <algorithm>
# include <iostream>
# include <cstdio>
# include <cstring>
# include <queue>
# define R register
# define LL long long
# define inf 999999999

using namespace std;

int n,m,up[10010],down[10010],a[10010],b[10010],f[10010][1010],k,gd[10010],g;

inline int in(R int &a){
    R char c = getchar();R int x = 0,f = 1;
    while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}
    while(isdigit(c)) x = x*10+c-'0',c = getchar();
    a = x*f;
}

int main (){
    in(n),in(m),in(k);
 	n++;//整体往后挪一位
    for(R int i=2; i<=n; ++i)
    	for(R int j=0; j<=m+1; ++j)
    		f[i][j] = inf;//初始化
    for(R int i=1; i<n; ++i) in(up[i]),in(down[i]);
    for(R int i=1; i<=n; ++i) b[i] = m+1;
    for(R int i=1; i<=k; ++i) {
        R int d,x,y;
        in(d),in(x),in(y);
        gd[++g] = d+1;
        a[d+1] = x,b[d+1] = y;
    }
    sort(gd+1,gd+g+1);
    for(R int i=1; i<=m; ++i) f[1][i]=0;
    for(R int i=2; i<=n; ++i){
        for(R int j=1; j<=m; ++j){
	        if(j-up[i-1] > 0)
                f[i][j] = min(f[i][j],f[i-1][j-up[i-1]]+1),
                f[i][j] = min(f[i][j],f[i][j-up[i-1]]+1);
		}//往上跳

	    for(R int j=m-up[i-1]; j<=m; ++j)
        	if(j > 0)
                f[i][m] = min(f[i][m],f[i-1][j]+1),
        		f[i][m] = min(f[i][m],f[i][j]+1);
                //顶部特殊处理
	    for(R int j=a[i]+1; j<b[i]; ++j)
            if(j+down[i-1] <= m) f[i][j] = min(f[i][j],f[i-1][j+down[i-1]]);
            //往下降

		for(R int j=1; j<=a[i]; ++j) f[i][j] = inf;
		for(R int j=b[i]; j<=m; ++j) f[i][j] = inf;
        //将不合法状态重新赋值回去
    }

    R int ans = inf;

    for (R int i=a[n]+1; i<b[n]; ++i) ans = min(ans,f[n][i]);

    if(ans < inf) printf("1\n%d",ans);
    else{
        R int i = 1;
        for(; i<=g; ++i)
            for(R int j=a[gd[i]]+1; j<b[gd[i]]; ++j){
                if(f[gd[i]][j] < inf) break;
                if(j == b[gd[i]]-1){
                    printf("0\n%d",i-1);
                    return 0;
                }
            }
    }
    return 0;
}