我小黄鸟表示不服

---

这个题能转换成背包也是很神了……

状态

f[i][j]表示到坐标\((i,j)\)的最少点击次数，若无法到达，则置为\(inf\)

转移

以下代码片段可能比较迷乱……

• 预处理

  因为可以从第一列任何地方开始所以第一列都是\(0\)

  for(int i=1;i<=m;i++) dp[0][i]=0;

• 上升

  上升有可能是从前一列飞到这当前列(点了一次)，也有可能是在当前列点了好几次，可以把它看成完全背包

  for(int j=jum[i].x;j<=jum[i].x+m;j++)    dp[i][j]=min(dp[i-1][j-jum[i].x],dp[i][j-jum[i].x])+1;

  上升还要注意特判飞到顶部的情况，因为飞到顶部就不能再向上飞了

  for(int j=m+1;j<=jum[i].x+m;j++)    dp[i][m]=min(dp[i][m],dp[i][j]);

• 下降

  下降就只可能是从前一列掉下来的，也就是说在同一列只能下降一次，可以把它看成\(01\)背包

  for(int j=1;j<=m-jum[i].y;j++)    dp[i][j]=min(dp[i][j],dp[i-1][j+jum[i].y]);

• 无法通过

  也就是管子，赋值为\(inf\)

  for(int j=1;j
        
         high[i];j--) dp[i][j]=inf;
        

剩下要注意的就是输出了，其实也没什么要注意的，会了\(DP\),剩下的都好说……(但我就是不会DP！！！)

\(\tt{code}\)

#include
    
     #include
     
      #include
      
       #include
       
        #define inf 0x7ffffff#define gc getchar();using namespace std;int read(){int k=0;char c=gc;while(!isdigit(c))c=gc;while(isdigit(c)){k=k*10+c-48;c=gc;}return k;}int read_c(){int k=0;char c=gc;while(c<'a'||c>'z')c=gc;return c-'a';}struct hhh{    int x,y;}jum[10010];int high[10010],low[100010],flag[100010];int dp[10010][2010];int main(){    int n=read(),m=read(),k=read();    //=======处理信息    for(int i=1;i<=n;i++)      jum[i].x=read(),jum[i].y=read();    for(int i=1;i<=n;i++) low[i]=1, high[i]=m;    for(int i=1;i<=k;i++){        int p=read(),l=read(),h=read();        flag[p]=1; low[p]=l+1; high[p]=h-1;;        }    memset(dp,127,sizeof(dp));    //======DP主体    for(int i=1;i<=m;i++) dp[0][i]=0;    for(int i=1;i<=n;i++){        for(int j=jum[i].x;j<=jum[i].x+m;j++)          dp[i][j]=min(dp[i-1][j-jum[i].x],dp[i][j-jum[i].x])+1;                  for(int j=m+1;j<=jum[i].x+m;j++)          dp[i][m]=min(dp[i][m],dp[i][j]);                  for(int j=1;j<=m-jum[i].y;j++)          dp[i][j]=min(dp[i][j],dp[i-1][j+jum[i].y]);                  for(int j=1;j
        
         high[i];j--)          dp[i][j]=inf;    }    //输出答案    int ans=inf;    for(int i=low[n];i<=high[n];i++)      if(dp[n][i]<=100000)        ans=min(ans,dp[n][i]);    if(ans!=inf)      printf("1\n%d",ans);    else{        ans=0;        for(int i=1;i<=n;i++){            bool hhh=0;            for(int j=1;j<=m;j++)              if(dp[i][j]<=100000){                  if(flag[i]) ans++;                  hhh=1; break;              }            if(!hhh) break;        }        printf("0\n%d",ans);    }    return 0;}