#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int MAXN=10010; const int INF=20172136; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();} while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();} return x*f; } int n,m,k; int x[MAXN],y[MAXN],l[MAXN],h[MAXN],ispipe[MAXN],z; int dp[MAXN][1010]; int main() { n=read(),m=read(),k=read(); for(int i=0;i<n;i++) { x[i]=read(); y[i]=read(); l[i]=0; h[i]=m+1; } l[n]=0,h[n]=m+1; for(int i=0;i<k;i++) { z=read(); ispipe[z]=1; l[z]=read(); h[z]=read(); } for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j]=INF; dp[0][0]=INF; for(int i=1;i<=m;i++)dp[0][i]=0; for(int i=1;i<=n;i++) { for(int j=x[i-1];j<=m;j++) { if(j==m) { for(z=m-x[i-1];z<=m;z++) dp[i][j]=min(dp[i][j],min(dp[i-1][z]+1,dp[i][z]+1)); } dp[i][j]=min(dp[i][j],min(dp[i-1][j-x[i-1]]+1,dp[i][j-x[i-1]]+1)); } for(int j=min(1,l[i]+1);j<=min(m-y[i-1],h[i]-1);j++) dp[i][j]=min(dp[i][j],dp[i-1][j+y[i-1]]); for(int j=l[i];j>=1;j--)dp[i][j]=INF; for(int j=h[i];j<=m;j++)dp[i][j]=INF; } int ans=INF,ans2=k; bool FLAG=0; for(int i=n;i>=1;i--) { for(int j=l[i]+1;j<=h[i]-1;j++)ans=min(ans,dp[i][j]); if(ans<INF)break; if(ispipe[i])k--; } if(ans2==k)printf("1 %d ",ans); else printf("0 %d ",k); return 0; }
小细节：
1.可以把每一块地方弄一个底端为0顶端为m+1的水管 避免讨论 同时要在真正的水管处打Tag帮助最后计算不能全部通过的情况
2.小鸟飞到m高处并不会死 只是不能再往上飞了 所以要特判
3.往上飞是完全背包，往下掉是01背包 背包处理完要把不能到达（碰到管子）的点dp值设成INF
4.先考虑往上飞 在考虑往下掉
状态：dp[i][j]表示飞到[i][j]最少要按几下屏幕
转移就是小细节3+小细节2+小细节4
然后...然后就做完了啊
果然坐在鸡神旁边做题是有加成的
小细节细着细着就细完了