codeforce 2B_codeforce559div2b-程序员宅基地

技术标签: DP  

B. The least round way
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that

  • starts in the upper left cell of the matrix;
  • each following cell is to the right or down from the current cell;
  • the way ends in the bottom right cell.

Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

Input

The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).

Output

In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

Examples
input
3
1 2 3
4 5 6
7 8 9
output
0
DDRR

题解:对2的个数,5的个数Dp,取最小的,有0特判
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
using namespace std;
int a[1005][1005],dp1[1005][1005],dp2[1005][1005],n;
void dfs(int dp[1005][1005],int x,int y)//回溯记路径 ,从最后一个点开始,要么左要么上 
{
	if(x==1&&y==1)
	return;
	int x1=x-1,y1=y-1;
	if(x1>=1&&x1<=n&&y1>=1&&y1<=n)
	{
		if(dp[x1][y]>dp[x][y1])
		{
			dfs(dp,x,y1);
			printf("R");
		}
		else
		{
			dfs(dp,x1,y);
			printf("D");
		}
	}
	else if(x1<1||x1>n)
	{
		dfs(dp,x,y1);
		printf("R");
	}
    else if(y1<1||y1>n)
    {
    	dfs(dp,x1,y);
    	printf("D");
	}
} 
int main()
{
	int i,j,x,y,biao;
	while(~scanf("%d",&n))
	{
		biao=0;
		memset(dp1,0,sizeof(dp1));
		memset(dp2,0,sizeof(dp2));
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			if(a[i][j]==0)
			{
				x=i;
				y=j;
				biao=1;
				dp1[i][j]=1;
				dp2[i][j]=1;
			}
			else
			{
			int t=a[i][j];
			while(a[i][j]%5==0)
			{
				dp1[i][j]++;
				a[i][j]/=5;
			}
			while(t%2==0)
			{
				dp2[i][j]++;
				t/=2;
			}
			}
		}
	}
	for(i=2;i<=n;i++)
	{
		dp1[1][i]=dp1[1][i-1]+dp1[1][i];
		dp1[i][1]=dp1[i-1][1]+dp1[i][1];
		dp2[1][i]=dp2[1][i-1]+dp2[1][i];
		dp2[i][1]=dp2[i-1][1]+dp2[i][1];
	}
	for(i=2;i<=n;i++)
	{
		for(j=2;j<=n;j++)                                                                                                                                 
		dp1[i][j]+=min(dp1[i-1][j],dp1[i][j-1]);
	}
	for(i=2;i<=n;i++)
	{
		for(j=2;j<=n;j++)                                                                                                                                
		dp2[i][j]+=min(dp2[i-1][j],dp2[i][j-1]);	
	}
	if(biao==1)
	{
		if(min(dp1[n][n],dp2[n][n])>1)
		{
			printf("1\n");
			for(i=1;i<y;i++)
			printf("R");
			for(i=2;i<=n;i++)
			printf("D");
			for(i=y+1;i<=n;i++)
			printf("R");
			printf("\n");
		}
		else
		{
			if(dp1[n][n]<=1)
			{
	        printf("%d\n",dp1[n][n]);
	       dfs(dp1,n,n);
			}
			else
			{
	     printf("%d\n",dp2[n][n]);
	      dfs(dp2,n,n);
			}
		}
	}
	else
	{
    if(dp1[n][n]<dp2[n][n])
    {
    printf("%d\n",dp1[n][n]);
	dfs(dp1,n,n);
	}
	else
	{
	printf("%d\n",dp2[n][n]);
	dfs(dp2,n,n);
	}
	printf("\n");
}
}
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wenbo201/article/details/77835932

智能推荐

使用OpenCV实现抖音“蓝线挑战”特效以及本地测试_c# 抖音 特效-程序员宅基地

文章浏览阅读1k次,点赞3次,收藏6次。效果展示本项目通过Python-OpenCV实现抖音的“蓝线挑战”功能,即跟随视频中滑动的指示线实现多帧延迟,在视觉上出现上半部分图像停留的效果。功能复现采集视频,包括从本地读取视频格式和启动摄像头两种方式;提取帧,对每一帧单独处理;根据视频分辨率,绘制区域:上半部分绘制图片,下半部分绘制视频;根据需求添加辅助;测试并完成创意视频录制。获取视频帧通过OpenCV内建函数cv2.VideoCapture实现视频帧截取。使用命令行参数解析包argparse设置程序的调用指令:无输入时打开摄_c# 抖音 特效

opencv系列文章之使用dnn模块调用tensorflow、Caffe和Torch/PyTorch深度学习模型_lprnet能否脱离深度学习框架直接运用opencv的dnn模块-程序员宅基地

文章浏览阅读2.6k次。深度学习有多厉害,就业前景有多开阔,我想每个学习计算机的人都能有所体会。Caffe、Tensorflow、Pytorch、Keras、mxnet等等深度学习框架,给了深度学习开发人员极大的方便,但他们部署起来却依旧较难!OpenCV自3.1版本其就在contrib中加入了DNN模块。到3.3版本时,将DNN模块由contrib提升到了正式代码块中。该DNN模块支持加载训练好的模型(即:这些模型需要实现在Caffe、TensorFlow、Torch/PyTorch等深度学习框架中提取训练好),并执行前向传播._lprnet能否脱离深度学习框架直接运用opencv的dnn模块

安装 torch1.0.0_安装torch1.0.0 cuda版本-程序员宅基地

文章浏览阅读2k次,点赞2次,收藏3次。window系统,pip, python3.6,none CUDA,参考:安装最新pytorch1.0.0打开cmd切换到python编程环境(比如:activate pytorch)下载相对应的whl,我下的是wins,python3.6版本的下载完成后,将该whl文件放在python相同的目录下即可(比如cd D:\anaconda3\anaconda3\envs\pytorch)在cmd中输入:pip install torch-1.0.0-cp36-cp3._安装torch1.0.0 cuda版本

2016"百度之星" - 初赛(Astar Round2B)_百度之星 2016初赛-程序员宅基地

文章浏览阅读901次。区间的价值Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 685 Accepted Submission(s): 343Problem Description我们定义“区间的价值”为一段区间的最大值*最小值。_百度之星 2016初赛

知识图谱的构建与质量评估_知识图谱质量评估-程序员宅基地

文章浏览阅读1.2w次,点赞11次,收藏39次。本文由知识图谱的结构构建,实体抽取,实体关系和属性抽取,知识图谱评估,知识图谱精炼六个部分组成。一、知识图谱构建知识图谱在目前知识体系中的三种组织分类:Ontology:树状结构,关系是严格的IsA关系,便于知识推理,但没法表达出概念和关系的多样性Taxonomy:树状结构,关系包含一般的上位词-下位词关系(Hypernym-Hyponym),关系的丰富影响了知识推理的难度,易造成歧义。Taxonomy也是我们当前最常用的知识图谱分类方法。Folksonomy:非层级的结构,全部节点以标签分类,_知识图谱质量评估

Linux网络设置--------教你如何配置双网卡进行上网-----一个挂了另一个顶替---------_linux两张网卡打开一个另一个会关掉-程序员宅基地

文章浏览阅读3k次,点赞2次,收藏9次。文章目录一、查看网络配置1.1 查看网络接口信息1.2 查看主机名称hostname1.3 查看路由条目route1.4 查看网络连接情况netstat1.5 获取socket统计信息ss二、测试网络连接2.1 测试网络连接ping2.2 跟踪数据包traceroute2.3 域名解析nslookup三、 设置网络地址参数3.1 设置网络地址参数的方式3.2 设置网络接口参数3.3 设置路由记录route3.4 修改主机名hostname3.5 网络接口配置文件3.6 启用、禁用网络接口配置3.7 主机名配_linux两张网卡打开一个另一个会关掉

随便推点

在MyEclipse8.5中复制项目或者导入项目(步骤及注意事项)_myesclipse8.5的项目导入rsclipse还能用吗-程序员宅基地

文章浏览阅读6.6k次。1 直接对需要拷贝的工程进行ctrl+c,然后ctrl+v,然后把工程名修改,然后右击工程选择最后一项,找到MyEclipse选项下边的web选项,把web context-root改为新的工程名字即可 2 导入工程,file-->import--->general--->existing project into workspace--->browser 找到你想要导入的工程,左下角的copy projects into workspace一定要选上,如果工程的jre _myesclipse8.5的项目导入rsclipse还能用吗

CentOS 8.x 下安装.Net 5 SDK/运行时_dotnet -sdk 5-程序员宅基地

文章浏览阅读2.2k次。0 运行环境[root@ZSSM01 ~]# lsb_release -a LSB Version: :core-4.1-amd64:core-4.1-noarchDistributor ID: CentOSDescription: CentOS Linux release 8.3.2011Release: 8.3.2011Codename: n/a1 目标安装.Net 5 SDK或者运行时2 安装方法安装之前,请先看第四部分参考文件。2.1 安_dotnet -sdk 5

element 搜索匹配_elementUI最新版的el-select使用filterable无效无法匹配正确搜索结果的Bug解决办法...-程序员宅基地

文章浏览阅读911次。Bug描述:今天做开发时遇到一个elementUI存在的bug。当el-select使用filterable功能搜索时,如果你恰巧使用的是微软拼音输入法,那么你有可能会遇到搜索结果和输入的值不匹配,如下图:我输入的是黄金,结果却显示有双皮蛋,龙须面。 复现办法:打开https://element.eleme.cn/#/zh-CN/component/select定位到【可以利用搜索功能快速查找选项..._ui-select option超过1000无法通过filter获取

浅谈购物车存储方式_储蓄存款购物车模式-程序员宅基地

文章浏览阅读3.8k次。在博客园里看了大家写的很多精彩的文章。忍不住,自己也想写写,但水平确实有限。一直不知道如何下笔,写的不好,欢迎大家拍砖。自己做电商也有3年多了,是不是可以写写电商基本的购物车实现呢。目前我们使用购物车的存储方式主要有:Session方式,Cookie方式,数据库存储,我们来一一分析优缺点。1.Session(Memcached)方式 优点:购物车信息保存在服务端,可以保存1M 信息。 ..._储蓄存款购物车模式

eclipse设置自动保存_eclipse mosquitto关机保存记录-程序员宅基地

文章浏览阅读3.6k次,点赞5次,收藏6次。eclipse不像idea有自动保存的功能,下面的设置也没有做到自动保存代码,只是在编译或运行时自动保存代码,建议还是使用ctrl+s或ctrl+shift+s保存代码1.window-->preferences-->General-->workspace-->save automatically before build2.window-->p..._eclipse mosquitto关机保存记录

阻止微信网页缓存_微信禁止页面缓存-程序员宅基地

文章浏览阅读680次。转自: http://www.cnblogs.com/zx3707/p/5893516.html做微网站建设的童鞋都知道,微网站就是一个普通的手机网站,只不过是适应的屏幕的大小,其它的与普通网站没有什么区别,现在市场有的微信网站就有数的那几种,完全只是选板,还没有普及到跟做网站的一样普及的地步,再说能不能普通还是两说的事,看看企鹅怎么修行了 闲话少说,本人对微信网站没有多大深入了解只是知道一点,_微信禁止页面缓存

推荐文章

热门文章

相关标签