设 \(f_{i, j}\) 表示走到点 \((i, j)\) 获得因数 2 的最小数量。
设 \(g_{i, j}\) 表示走到点 \((i, j)\) 获得因数 5 的最小数量。
那么到点 \((i, j)\) 胃部获得的最小 0 的个数为 \(\min(f_{i,j}, g_{i, j})\),因为如果选择数量小的那个因数,另外一个因数的个数一定多于它,就会往后加一个 0,这样就使得 0 的个数最小。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, a[N][N], y2[N][N], y5[N][N], f2[N][N], f5[N][N];
pair<int, int> lz2[N][N], lz5[N][N];
int num_0_x;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (!a[i][j]) {
num_0_x = i;
}
else {
while (a[i][j] % 2 == 0) {
y2[i][j]++;
a[i][j] /= 2;
}
while (a[i][j] % 5 == 0) {
y5[i][j]++;
a[i][j] /= 5;
}
}
}
}
memset(f2, 0x3f, sizeof(f2));
memset(f5, 0x3f, sizeof(f5));
f2[0][1] = f5[0][1] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (f2[i - 1][j] < f2[i][j - 1]) {
f2[i][j] = f2[i - 1][j] + y2[i][j];
lz2[i][j] = {i - 1, j};
}
else {
f2[i][j] = f2[i][j - 1] + y2[i][j];
lz2[i][j] = {i, j - 1};
}
if (f5[i - 1][j] < f5[i][j - 1]) {
f5[i][j] = f5[i - 1][j] + y5[i][j];
lz5[i][j] = {i - 1, j};
}
else {
f5[i][j] = f5[i][j - 1] + y5[i][j];
lz5[i][j] = {i, j - 1};
}
}
}
int ans = min(f2[n][n], f5[n][n]);
string s;
if (ans == f2[n][n]) {
int x = n, y = n;
while (x >= 1 && y >= 1) {
if (lz2[x][y].first == x - 1) {
x--;
s.push_back('D');
}
else {
y--;
s.push_back('R');
}
}
}
else {
int x = n, y = n;
while (x >= 1 && y >= 1) {
if (lz5[x][y].first == x - 1) {
x--;
s.push_back('D');
}
else {
y--;
s.push_back('R');
}
}
}
s.pop_back();
reverse(s.begin(), s.end());
if (num_0_x && ans > 1) {
cout << "1\n";
for (int i = 2; i <= num_0_x; i++) cout << "D";
for (int i = 2; i <= n; i++) cout << "R";
for (int i = num_0_x + 1; i <= n; i++) cout << "D";
}
else {
cout << ans << '\n';
cout << s << '\n';
}
return 0;
}
标签:f2,f5,int,back,else,--,way,CF2B,round
From: https://www.cnblogs.com/Yuan-Jiawei/p/18337321