一个很简单的BFS都调不出来,自闭了
//BFS,两种决策要么上升,要么下降,边界很简单
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,k,flag,idx,can,len,res=INF,ans=-INF;
int up[10010],down[10010];
struct node{
int x,y,cnt;
};//小鸟此时横坐标和纵坐标和点击屏幕的次数和能通过几个管道
struct node2{
int h,l;//h是上边缘,l是下边缘,pos是坐标
}g[10010];//管子的属性
void bfs(int s)
{
queue<node> q;
q.push((node){0,s,0});//横坐标,纵坐标,按屏幕的次数
while(q.size())
{
node u=q.front();
q.pop();
int x=u.x;//横坐标
int y=u.y;//纵坐标
int cnt=u.cnt;
if(y>m)
y=m;
if(y>=g[x].h)//横坐标为x时管子的上边缘
continue;
if(y<=g[x].l||y<=0)//横坐标为x时管子的下边缘
continue;
if(x==n)
{
flag=1;
ans=cnt;
break;
}
q.push((node){x+1,y+up[x],cnt+1});//点屏幕,飞一下
q.push((node){x+1,y-down[x],cnt});//不点屏幕,降一下
}
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<=n-1;i++)
{
scanf("%d%d",&up[i],&down[i]);//横坐标为i时进行操作的up and down
}
for(int i=0;i<=n;i++)
{
g[i].h=INF;
g[i].l=-INF;
}
for(int i=1;i<=k;i++)
{
int pos,l,h;
scanf("%d%d%d",&pos,&l,&h);
g[pos].l=l,g[pos].h=h;
}
for(int i=1;i<=m;i++)//初始高度
{
bfs(i);
res=min(res,ans);//最少需要点击屏幕的次数
}
cout<<"1"<<endl<<res;
return 0;
}