实现诡异类(DP)
设状态(f[i][j])表示到第(i)个位置高度为(j)为止，所用的最小步数。
转移时注意向上移是个完全背包，向下移是个(01)背包。
同时对(f[i][m]=max(f[i][m],f[i][j])(1leq jleq m+X[i]))
转移完后处理一下管道的情况（将有管道的地方变为( ext{INF})）
最后统计答案即可。
#include<bits/stdc++.h>
using namespace std;
namespace AE86
{
const int bufl=1<<15;
char buf[bufl],*s=buf,*t=buf;
inline int fetch()
{
if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
return*s++;
}
inline int read()
{
int a=0,b=1,c=fetch();
while(!isdigit(c)) b^=c=='-',c=fetch();
while(isdigit(c)) a=a*10+c-48,c=fetch();
return b?a:-a;
}
}
const int N=1e4+10;
const int M=2e3+10;
int n,m,k,Ans;
int f[N][M],X[N],Y[N];
struct Channel {int Jud,Up,Dw;} Lin[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
n=AE86::read(),m=AE86::read(),k=AE86::read();
for(int i=1;i<=n;i++) X[i]=AE86::read(),Y[i]=AE86::read();
for(int i=1;i<=n;i++) Lin[i].Up=m+1,Lin[i].Dw=0,Lin[i].Jud=0;
for(int i=1,Pos;i<=k;i++)
{
Pos=AE86::read(),Lin[Pos].Jud=1;
Lin[Pos].Dw=AE86::read(),Lin[Pos].Up=AE86::read();
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;i++) f[0][i]=0;
for(int i=1;i<=n;i++)
{
for(int j=1+X[i];j<=m+X[i];j++)
f[i][j]=min(f[i][j-X[i]]+1,f[i-1][j-X[i]]+1);
for(int j=m+1;j<=m+X[i];j++) f[i][m]=min(f[i][m],f[i][j]);
for(int j=1;j<=m-Y[i];j++) f[i][j]=min(f[i][j],f[i-1][j+Y[i]]);
for(int j=1;j<=Lin[i].Dw;j++) f[i][j]=f[0][0];
for(int j=m;j>=Lin[i].Up;j--) f[i][j]=f[0][0];
}
Ans=f[0][0];
for(int i=1;i<=m;i++) Ans=min(Ans,f[n][i]);
if(Ans<f[0][0]) printf("1
%d
",Ans);
else
{
int i,j;Ans=0;
for(i=n;i>=1;i--)
{
for(j=1;j<=m;j++)
if(f[i][j]<f[0][0]) break;
if(j!=m+1) break;
}
for(int j=1;j<=i;j++) Ans+=(bool)Lin[j].Jud;
printf("0
%d
",Ans);
}
}