CF2 B. The least round way

题目传送门：https://codeforces.com/problemset/problem/2/B

题目大意：
给定 \(n\times n\) 的数表，求一条从左上角到右下角的路径，使得路径上各数相乘所得的后置零尽可能少，输出操作序列（DR）

由于后置零仅可能由\(2\times 5\)得到，故我们将所有数中的2,5质因子个数求出来，然后找到一条2的个数或5的个数最少的路径即可。

/*program from Wolfycz*/
#include
#include
#include
#include
#include
#include
#include
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(x) ((x)*(x))
#define pii pair
#define int_inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
templateinline T frd(T x){
	int f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
templateinline T read(T x){
	int f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int N=1e3;
int F[2][N+10][N+10],opt;
pii Frm[2][N+10][N+10];
char Ans[N+10];
char Direction(int sx,int sy,int ex,int ey){
	if (sx+1==ex)	return 'D';
	if (sy+1==ey)	return 'R';
	return 0;
}
void solve(int x,int y){
	int len=0;
	while (x>1||y>1){
		pii temp=Frm[opt][x][y];
		Ans[len++]=Direction(temp.Fi,temp.Se,x,y);
		x=temp.Fi,y=temp.Se;
	}
	reverse(Ans,Ans+len);
	printf("%s\n",Ans);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n=read(0),Flag=0,Zx,Zy;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			int x=read(0);
			if (!x){
				Zx=i,Zy=j;
				Flag|=1;
				continue;
			}
			while (x%2==0)	F[0][i][j]++,x/=2;
			while (x%5==0)	F[1][i][j]++,x/=5;
		}
	}
	for (int K=0;K<2;K++){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				if (i==1&&j==1)	continue;
				if (i==1){
					F[K][i][j]+=F[K][i][j-1];
					Frm[K][i][j]=MK(i,j-1);
					continue;
				}
				if (j==1){
					F[K][i][j]+=F[K][i-1][j];
					Frm[K][i][j]=MK(i-1,j);
					continue;
				}
				F[K][i][j]+=min(F[K][i-1][j],F[K][i][j-1]);
				Frm[K][i][j]=F[K][i-1][j]1&&Flag){
		printf("1\n");
		for (int i=1;i
基础算法动态规划基础算法BFSOJCodeforces

相关

标签