[洛谷 1941][NOIP2014]飞扬的小鸟

题目链接

https://www.luogu.org/problem/P1941

题解

设 \(f(i,j)\) 表示横坐标为 \(i\)，纵坐标为 \(j\) 时的最小点击次数。

初始时 \(f(0,j)=0\)，其余为正无穷。

有上升和下降两种转移。

对于上升，可以从如下两个状态转移：

• 前一秒的状态，即 \(f(i-1,j-x_i)\)；
• 这一秒的状态，即 \(f(i,j-x_i)\)。

对于下降，则只能从前一秒的状态（即 \(f(i-1,j+y_i)\)）转移而来。

对于高度超过上界的转移，我们直接将其转移到高度为上界的状态即可。

如果存在一个 \(f(n,j)\) 的值不为正无穷，表明可以抵达，否则不能抵达。不能抵达时，只需找到一个使 \(f(i,j)\) 不为正无穷的最大的 \(i\) 即可确定最远距离。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define INF 0x3f3f3f3f
using namespace std;
int d[10005],u[10005],x[10005],y[10005],f[10005][2005];
set<int> s;
int main()
{
 int n,m,k;
 scanf("%d%d%d",&n,&m,&k);
 for(int i=1;i<=n;i++)
 {
  scanf("%d%d",&x[i],&y[i]);
  d[i]=1;
  u[i]=m;
 }
 for(int i=1;i<=k;i++)
 {
  int p,l,h;
  scanf("%d%d%d",&p,&l,&h);
  d[p]=l+1,u[p]=h-1;
  s.insert(p);
 }
 memset(f,INF,sizeof(f));
 for(int i=1;i<=m;i++)
  f[0][i]=0;
 for(int i=1;i<=n;i++)
 {
  for(int j=x[i]+1;j<=x[i]+m;j++)
   f[i][j]=min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1);
  for(int j=m+1;j<=x[i]+m;j++)
   f[i][m]=min(f[i][j],f[i][m]);
  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<d[i];j++)
   f[i][j]=INF;
  for(int j=u[i]+1;j<=m;j++)
   f[i][j]=INF;
 }
 int ans=INF;
 for(int i=1;i<=m;i++)
  ans=min(ans,f[n][i]);
 if(ans!=INF)printf("1\n%d\n",ans);
 else
 {
  ans=0;
  for(int i=1;i<=n;i++)
  {
   int tmp=INF;
   for(int j=1;j<=m;j++)
    tmp=min(f[i][j],tmp);
   if(tmp==INF)
   {
    printf("0\n%d\n",ans);
    break;
   }
   ans+=s.count(i);
  }
 }
 return 0;
}