【题解】【CF2B The least round way】

本文主要是介绍【题解】【CF2B The least round way】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

我已经菜得连绿题都不会了。。。

Solution

首先要注意矩阵中有可能是0，因此要特判是否有0，最后跟不经过0的最优解进行比较。
要使尾0最少，发现只有质因子2和5的个数有贡献，因此可以设f[i][j][k]表示从(1,1)到(i,j)在有k个质因子2的情况下（若5的质因子多于2，则令k为负数，让下标加上一个M即可），最少有多少个0。
但这个状态就已经炸掉了，完全想不出怎么优化。。。
但其实这里用一个贪心就可以了。考虑求出num2，num5分别表示从起点到终点最少经过几个2,5。
两者取min即为答案。
证明如下：
一定可以构造出一组解符合条件，即num2和num5中较小的一条路径。
且不存在更优的方案，因为其他的路径中的min(num2,num5)一定不小于这条路径。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read()
{
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=~(x-1);
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=1005;
int n,a[N][N],w[2][N][N],f[2][N][N],sx,sy,pre[2][N][N];
void print(int p,int x,int y)
{
	if(x==1&&y==1) return;
	if(pre[p][x][y]){
		print(p,x-1,y);putchar('D');
	}
	else{
		print(p,x,y-1);putchar('R');
	}
}
signed main()
{
	memset(f,0x3f,sizeof f);
    n=read();
    for(int i=1;i<=n;++i)
    {
    	for(int j=1;j<=n;++j)
    	{
    		a[i][j]=read();
    		if(a[i][j]==0) {
    			sx=i,sy=j;
    			continue;
			}
    		while(a[i][j]%2==0) a[i][j]/=2,w[0][i][j]++;
    		while(a[i][j]%5==0) a[i][j]/=5,w[1][i][j]++;
		}
	}
	if(a[1][1]==0){
		puts("1");for(int i=1;i<n;++i) putchar('R');for(int i=1;i<n;++i) putchar('D');
		return 0;
	}
	f[0][1][1]=w[0][1][1];f[1][1][1]=w[1][1][1];
	for(int i=2;i<=n;++i) {
		if(a[1][i]==0) break;
		f[0][1][i]=f[0][1][i-1]+w[0][1][i],f[1][1][i]=f[1][1][i-1]+w[1][1][i];
	}
	for(int i=2;i<=n;++i){
		if(a[i][1]==0) break;
		f[1][i][1]=f[1][i-1][1]+w[1][i][1],f[0][i][1]=f[0][i-1][1]+w[0][i][1];pre[1][i][1]=pre[0][i][1]=1;
	}
	for(int i=2;i<=n;++i)
	{
		for(int j=2;j<=n;++j)
		{
			if(a[i][j]==0) continue;
			f[0][i][j]=min(f[0][i-1][j],f[0][i][j-1])+w[0][i][j];
			f[1][i][j]=min(f[1][i-1][j],f[1][i][j-1])+w[1][i][j];
			if(f[0][i-1][j]<f[0][i][j-1]) pre[0][i][j]=1;
			if(f[1][i-1][j]<f[1][i][j-1]) pre[1][i][j]=1;
		}
	}
	int ans=min(f[0][n][n],f[1][n][n]);int p=0;if(f[0][n][n]>f[1][n][n]) p=1;
	if(sx)
	{
		if(ans) {
			puts("1");
			for(int i=1;i<sx;++i) putchar('D');
			for(int j=1;j<sy;++j) putchar('R');
			for(int i=1;i<=n-sx;++i) putchar('D');
			for(int j=1;j<=n-sy;++j) putchar('R');
			return 0;
		}
		puts("0");
		print(p,n,n);
		return 0;
	}
	write(ans);puts("");print(p,n,n);
	return 0;
}

这篇关于【题解】【CF2B The least round way】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！