目录
显示
题目链接
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; }