飞扬的小鸟
分析
直接进入正题
单取一个位置来看,假设当前为第 i 列,高度为 j ,这个高度要么是从位置 i - 1 落下来,要么则是点击屏幕飞上来的,这难道不是一个状态转移方程?即枚举当前位置和高度,设为f [ i ] [ j ],则
但是注意,这个空间是有限的——高度不可能低于1或高于m,所以得单独列出考虑。
scanf("%d%d%d",&n,&m,&k);//输入
for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),bird[i].l=0,bird[i].h=m+1;
//每一个位置的可行移动位置以及点击与未点击变换的高度
for (int i=1;i<=k;i++)
{
int x;
scanf("%d",&x);
flag[x]=1;
scanf("%d%d",&bird[x].l,&bird[x].h);
}//输入管道
memset(f[0],0,sizeof(f[0]));
for (int i=1;i<=n;i++)
{
int op=m+a[i];
for (int j=a[i]+1;j<=op;j++) f[i][j]=min(f[i-1][j-a[i]],f[i][j-a[i]])+1;
//假设当时没有m的限制
for (int j=m+1;j<=op;j++) f[i][m]=min(f[i][m],f[i][j]);
//重新更新此时到达高度m的最小步数
for (int j=m-b[i];j>=1;j--) f[i][j]=min(f[i][j],f[i-1][j+b[i]]);
//不点击屏幕
for (int j=1;j<=bird[i].l;j++) f[i][j]=INF;
for (int j=bird[i].h;j<=m;j++) f[i][j]=INF;
//把限制区域的状态设为不合法即可
}
考虑和发育不合法的情况。合法就不用说了,如果不合法,那么肯定是在某一次管道就没了(QwQ,这游戏还能这样)。那么后续状态都无法得到转移。那么我们直接找到最后一次的合法状态,然后找到他们之间有多少管道即可。
代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e4+3,M=2e3+2;
int n,m,k;
int a[N],b[N];
int f[N][M];
bool flag[N];
struct Bird
{
int p,l,h;
}bird[N];
int main()
{
memset(f,0x3f,sizeof(f));
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),bird[i].l=0,bird[i].h=m+1;
for (int i=1;i<=k;i++)
{
int x;
scanf("%d",&x);
flag[x]=1;
scanf("%d%d",&bird[x].l,&bird[x].h);
}
memset(f[0],0,sizeof(f[0]));
for (int i=1;i<=n;i++)
{
int op=m+a[i];
for (int j=a[i]+1;j<=op;j++) f[i][j]=min(f[i-1][j-a[i]],f[i][j-a[i]])+1;
for (int j=m+1;j<=op;j++) f[i][m]=min(f[i][m],f[i][j]);
for (int j=m-b[i];j>=1;j--) f[i][j]=min(f[i][j],f[i-1][j+b[i]]);
for (int j=1;j<=bird[i].l;j++) f[i][j]=INF;
for (int j=bird[i].h;j<=m;j++) f[i][j]=INF;
}
int res=INF;
for (int i=1;i<=m;i++) res=min(f[n][i],res);
if(res>1e9)
{
printf("0\n");
int i;
for(i=n;i>=1;i--)
{
bool flg=false;
for (int j=m;j>=1;j--) if(f[i][j]<INF) flg=1;
if(flg) break;
}
int ans=0;
for (int k=1;k<=i;k++) if(flag[k]) ans++;
printf("%d\n",ans);
return 0;
}
printf("1\n%d",res);
return 0;
}