首页 技术 正文
技术 2022年11月24日
0 收藏 861 点赞 2,727 浏览 1138 个字

题意:给你n行长度为m的01串(n<15,m<100) 。每次只能走一步,要将所有的1变为零,问最少的步数,注意从左下角开始,每次要将一层清完才能走到上一层,每次只有在第一列或者最后一列才能往上走一层,否则只能左右移动。

题解:由于清完当前层才能继续上一层,所以必然存在一个递推关系。先递推预处理,然后输出ans即可。用far来存最远的那个1,如果这层没有1,假设有一个,令其距离为1

具体看代码注释吧。

坑:没考虑没有1以及只有1层的情况

#define  _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
int m, n, len;
int dp[][];//清完i层回到最左0右1 所需的min
int far[][];//每层楼离左0右1 最远的灯
int no[];
int main() {
while (cin >> n >> m) {
for (int i = ; i <= n; i++) {//从顶层开始输入
string s;
cin >> s;
len = s.length();
int j;
int ok = ;
for (j = ; j < len - ; j++) if (s[j] == '') { far[n + - i][] = len - j; break; } for (j = len - ; j > ; j--)if (s[j] == '') { far[n + - i][] = j + ; break; }
for (j = ; j < len; j++) { if (s[j] == '') ok = ; }
if (ok == )far[n + - i][] = , far[n + - i][] = , no[n + - i] = ;
}
//如果某层没灯+1跳过:
if (no[]) far[][] = ;//floor 1 no lamp
dp[][] = len - ; dp[][] = far[][] * - ;//wa这儿了,忘记考虑只有1层,应该改far
for (int i = ; i <= n; i++) {
for (int j = ; j <= ; j++)dp[i][j] = maxn;
dp[i][] = min(max(, dp[i - ][] + far[i][] * - ), dp[i - ][] + len);
dp[i][] = min(max(, dp[i - ][] + far[i][] * - ), dp[i - ][] + len);
} //1st floor start from left,
int k = n;
while (no[k])k--; int ans = min(dp[k - ][] + far[k][], dp[k - ][] + far[k][]);
//1层
if (k == ) {
far[][]--; ans = far[][];
}
cout << ans << endl;
}
cin >> n;
}
 

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/142076.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站