飞翔的小鸟

QAQ


但是转移时需要先转移上升然后下落。
还有就是管内也要转移（否则跳k步可以跳上去的不能上去）

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
struct node{
    int x,y;
}a[11000];
struct Node{
    int s,x;
    bool flag;
}b[11000];
int inf=99999999;
int n,m,k;
int dp[11000][1100];
int num;
int main()
{
    memset(dp,127/3,sizeof(dp));
    inf=dp[0][0];
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
     scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=n+1;i++) b[i].s=m+1,b[i].x=0;
    for(int i=1,x,y,c;i<=k;i++)
     scanf("%d%d%d",&x,&y,&c),b[x+1].s=c,b[x+1].x=y,b[x+1].flag=1;
    for(int i=b[1].x+1;i<=b[1].s-1;i++) dp[1][i]=0;
    //if(b[1].flag) num++;
    for(int i=2;i<=n+1;i++)
    {
     // int m1,m2; 
       int f=0;
       for(int j=a[i-1].x+1;j<=m;j++)
        dp[i][j]=min(min(dp[i-1][j-a[i-1].x],dp[i][j-a[i-1].x])+1,dp[i][j]);
       for(int j=m-a[i-1].x;j<=m;j++)
        dp[i][m]=min(min(dp[i-1][j],dp[i][j])+1,dp[i][m]);
       for(int j=b[i].x+1;j<b[i].s;j++)
        if(a[i-1].y+j<=m) dp[i][j]=min(dp[i][j],dp[i-1][j+a[i-1].y]);
       for(int j=1;j<=b[i].x;j++)
        dp[i][j]=inf;
       for(int j=b[i].s;j<=m;j++)
        dp[i][j]=inf;
        //if(b[i].flag==1&&f==0&&dp[i][j]!=inf) num++,f=1;
        /*for(int j=b[i].x+1;j<b[i].s;j++)
        printf("%d %d %d\n",i,j,dp[i][j]);*/
    }
    for(int i=1;i<=n;i++)
     if(b[i].flag)
      for(int j=b[i].x;j<=b[i].s;j++)
       if(dp[i][j]!=inf)
       {
        num++;
        break;
       }
    int min1=inf;
    for(int i=1;i<=m;i++)
     min1=min(dp[n+1][i],min1);
    //printf("%d\n",dp[n+1][i]);
    if(min1==inf)
    printf("0\n%d",num);
    else
    printf("1\n%d",min1);
}