P1941 飞扬的小鸟

EricQian · 2020-09-11 23:09:57 · 个人记录

\leftarrow last~page

P1941 飞扬的小鸟

算法：01 背包 + 完全背包 。

状态：设 dp[i][j] 表示横坐标为 i 高度为 j 的最少点击次数 。

1. 上升 ：完全背包 转移方式

2. 下降 ：01 背包 转移方式

3. 超过 m 变为 m ： 特判

代码：

for(int i=1;i<=n;i++) Low[i]=1,High[i]=m;
for(int i=1;i<=k;i++) p=rd(),e[p]=1,Low[p]=rd()+1,High[p]=rd()-1;
memset(g,inf,sizeof(g));
for(int i=1;i<=m;i++) g[i]=0;
for(int i=1;i<=n;i++)
{
     memset(f,inf,sizeof(f));
     for(int j=x[i];j<=x[i]+m;j++) f[j]=min(f[j-x[i]]+1,g[j-x[i]]+1); // 完全背包
     for(int j=m+1;j<=m+x[i];j++) f[m]=min(f[j],f[m]); // 特判超过 m
     for(int j=1;j<=m-y[i];j++) f[j]=min(f[j],g[j+y[i]]); // 01 背包
     for(int j=1;j<Low[i];j++) f[j]=inf;
     for(int j=High[i]+1;j<=m;j++) f[j]=inf; // 不可行方案
     if(e[i]) for(int j=Low[i];j<=High[i];j++) if(f[j]<inf) { cnt++; break; } // 统计通过的管道数
     memcpy(g,f,sizeof(g));
}
for(int i=1;i<=m;i++) ans=min(ans,g[i]);
if(ans!=inf) printf("1\n%d\n",ans);
else printf("0\n%d\n",cnt);