洛谷P1941飞扬的小鸟——细节DP
2024-09-04 13:13:58
题目:https://www.luogu.org/problemnew/show/P1941
此题主要注意许多细节,详见代码。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,up[10005],down[10005],p[10005],l[10005],h[10005],f[10005][1005],wall[10005];
int INF=1e7;
bool vis[10005];
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++)
scanf("%d%d",&up[i],&down[i]);
for(int i=1;i<=k;i++)
scanf("%d%d%d",&p[i],&l[i],&h[i]),wall[p[i]]=i;
memset(f,11,sizeof f);
for(int j=1;j<=m;j++)f[0][j]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
// if(wall[i]&&(j<=l[wall[i]]||j>=h[wall[i]]))continue;//不可部分!
if(j==m)
for(int k=0;k<=up[i-1]&&j-k>0;k++)//k=0
{
if(!wall[i-1]||(wall[i-1]&&j-k>l[wall[i-1]]&&j-k<h[wall[i-1]]))
f[i][j]=min(f[i][j],min(f[i-1][j-k]+1,f[i][j-k]+1));
else f[i][j]=min(f[i][j],f[i][j-k]+1);
}
else if(j-up[i-1]>0)
{
if(!wall[i-1]||(wall[i-1]&&j-up[i-1]>l[wall[i-1]]&&j-up[i-1]<h[wall[i-1]]))
f[i][j]=min(f[i][j],min(f[i-1][j-up[i-1]]+1,f[i][j-up[i-1]]+1));
else f[i][j]=min(f[i][j],f[i][j-up[i-1]]+1);
}
//不可又降又升
if(f[i][j]<INF&&(!wall[i]||(wall[i]&&j>l[wall[i]]&&j<h[wall[i]])))
vis[i]=1;
}
for(int j=1;j<=m;j++)
if(j+down[i-1]<=m&&
(!wall[i-1]||(wall[i-1]&&j+down[i-1]>l[wall[i-1]]&&j+down[i-1]<h[wall[i-1]])))
{
f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);
if(f[i][j]<INF&&(!wall[i]||(wall[i]&&j>l[wall[i]]&&j<h[wall[i]])))
vis[i]=1;
}
}
if(vis[n])
{
int mn=INF;
for(int j=1;j<=m;j++)
if(f[n][j]<mn)mn=f[n][j];
printf("1\n%d",mn);
}
else
{
int nw,ans=0;
for(int i=n;i>=1;i--)
if(vis[i])
{
nw=i;
break;
}
for(int i=1;i<=nw;i++)
if(wall[i])ans++;
printf("0\n%d",ans);
}
return 0;
}
最新文章
- jQuery知识点总结(第一天)
- Mastering Web Application Development with AngularJS 读书笔记(一)
- Enum:EXTENDED LIGHTS OUT(POJ 1222)
- loadrunner11录制报 NOT PROXIED!错误,无法生成脚本
- [Objective-C]__bridge,__bridge_retained和__bridge_transfer的意思,区别与使用
- [TypeScript] Using Exclude and RootDir until File Globs Lands in 2.0.
- UML-图的意义
- ASP.NET之电子商务系统开发-1(数据列表)
- 8张图理解Java(转)
- Android开源项目pulltorefresh分析与简单使用
- C#中利用双缓冲技术解决绘图闪屏问题。
- dubbo不完全指南
- VS2015中使用报表控件(ReportViewer)的方法
- pytest pluggy.manager.PluginValidationError: unknown hook &#39;pytest_namespace&#39;报错处理办法
- 解决 Files 的值";<;<;<;<;<;<;<; HEAD";无效。路径中具有非法字符
- C语言中数组变量和指针变量
- 目标检测:YOLO(v1 to v3)——学习笔记
- Vuejs——(13)组件——杂项
- Java学习笔记——IO操作之以图片地址下载图片
- Flink HA