题解 CF2B 【The least round way】

题意

在一个矩阵中做乘法，让结果的0最少。

题解

因为是矩阵乘法，0是2与5构成的，只要判断有几个2和5就可以。很容易想到使用dp。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int x,n;
int dp[N][N][2];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	int pos=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>x;
			if(x==0)
			{
				pos=i;
				continue;
			}
			int t=x;
			while(t%2==0) 
			{
				dp[i][j][0]++;
				t/=2;	
			}
			t=x;
			while(t%5==0) 
			{
				dp[i][j][1]++;
				t/=5;	
			}
		}
	}
	for(int i=2;i<=n;i++)
	{
		dp[i][1][0]+=dp[i-1][1][0];
		dp[i][1][1]+=dp[i-1][1][1];//初始化
		dp[1][i][0]+=dp[1][i-1][0];
		dp[1][i][1]+=dp[1][i-1][1];
	}	
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=n;j++)
		{
			dp[i][j][0]+=min(dp[i-1][j][0],dp[i][j-1][0]);
			dp[i][j][1]+=min(dp[i-1][j][1],dp[i][j-1][1]);
		}//开始dp
	}
	string ans;//string可以更方便操作
	int k=0;
	if(dp[n][n][0]>dp[n][n][1]) k=1;
	if(pos!=-1&&dp[n][n][k]>0)//特判
	{
		cout<<1<<endl;
		for(int i=1;i<pos;i++) cout<<"D";
		for(int i=1;i<n;i++) cout<<"R";
		for(int i=pos;i<n;i++) cout<<"D";
		return 0; 
	}
	int i=n,j=n;
	while(true)
	{
		if(dp[i-1][j][k]<dp[i][j-1][k])
		{
			i--;
			ans+="D";
		}
		else
		{
			j--;
			ans+="R";
		}
		if(i==1) 
		{
			for(int l=1;l<j;l++) ans+="R";
			break; 
		}
		if(j==1)
		{
			for(int l=1;l<i;l++) ans+="D";
			break; 
		}
	}
	cout<<dp[n][n][k]<<endl;
	for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
	return 0;
}