題目：The least round way

?

1000*1000的方陣，每個格子有一個非負整數，現在要從左上走到右下，每次只能向下或者向右走。目標是使得所有走的格子里的數的乘積里，末尾0的個數最少，要求輸出最有解和走法。

不用怎么想也知道基本是個dp了，可以發現其實只有2和5的因子是有用的，但是如果狀態同時記錄2和5的因子個數的話，就不好表示了。其實方法很簡單，對2個5分別做一次，第一次讓2盡量少，第二次讓5盡量少，兩個里面取個最小的就是答案了，應該不難證明。dp過程就比較普通了，記錄下路徑，最后輸出即可，不再贅述。

當然，本題是有一個比較大的trick的，就是如果其中有一個數字為0，那么最后的乘積可以為0，也就是答案至少可以是1。因此，只要先記錄下方陣中有沒有0，然后dp的時候強制不走0，最后輸出走0和不走0的最優解即可。

#include <cstdio> #include <algorithm>using namespace std;const int MAXN = 1024; int m2[MAXN][MAXN]; int m5[MAXN][MAXN]; int l2[MAXN][MAXN]; int l5[MAXN][MAXN]; int dp2[MAXN][MAXN]; int dp5[MAXN][MAXN]; int n; int zx, zy;void output(int ll[MAXN][MAXN], int x, int y) {if (x == 0 && y == 0)return;if (ll[x][y] == 0){output(ll, x - 1, y);putchar('D');}else{output(ll, x, y - 1);putchar('R');} }int main() {scanf("%d", &n);zx = zy = -1;for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){scanf("%d", &m2[i][j]);if (m2[i][j] != 0){m5[i][j] = 0;while (m2[i][j] % 5 == 0){++m5[i][j];m2[i][j] /= 5;}int t = 0;while (m2[i][j] % 2 == 0){++t;m2[i][j] /= 2;}m2[i][j] = t;}else{zx = i;zy = j;m2[i][j] = m5[i][j] = -1;}}}for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (m2[i][j] == -1)dp2[i][j] = -1;else{if (i == 0 && j == 0)dp2[i][j] = m2[i][j];else{dp2[i][j] = 100000000;if (i > 0 && dp2[i - 1][j] != -1 && dp2[i - 1][j] + m2[i][j] < dp2[i][j]){dp2[i][j] = dp2[i - 1][j] + m2[i][j];l2[i][j] = 0;}if (j > 0 && dp2[i][j - 1] != -1 && dp2[i][j - 1] + m2[i][j] < dp2[i][j]){dp2[i][j] = dp2[i][j - 1] + m2[i][j];l2[i][j] = 1;}if (dp2[i][j] == 100000000)dp2[i][j] = -1;}}}}for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (m5[i][j] == -1)dp5[i][j] = -1;else{if (i == 0 && j == 0)dp5[i][j] = m5[i][j];else{dp5[i][j] = 100000000;if (i > 0 && dp5[i - 1][j] != -1 && dp5[i - 1][j] + m5[i][j] < dp5[i][j]){dp5[i][j] = dp5[i - 1][j] + m5[i][j];l5[i][j] = 0;}if (j > 0 && dp5[i][j - 1] != -1 && dp5[i][j - 1] + m5[i][j] < dp5[i][j]){dp5[i][j] = dp5[i][j - 1] + m5[i][j];l5[i][j] = 1;}if (dp5[i][j] == 100000000)dp5[i][j] = -1;}}}}if (dp2[n - 1][n - 1] == -1){printf("1\n");for (int i = 0; i < n - 1; ++i)putchar('D');for (int i = 0; i < n - 1; ++i)putchar('R');puts("");}else{int now = min(dp2[n - 1][n - 1], dp5[n - 1][n - 1]);if (zx != -1 && now >= 1){printf("1\n");for (int i = 0; i < zx; ++i)putchar('D');for (int i = 0; i < n - 1; ++i)putchar('R');for (int i = zx; i < n - 1; ++i)putchar('D');puts("");}else{printf("%d\n", now);if (dp2[n - 1][n - 1] < dp5[n - 1][n - 1])output(l2, n - 1, n - 1);elseoutput(l5, n - 1, n - 1);puts("");}}return 0; }

?

總結

以上是生活随笔為你收集整理的Codeforces Beta Round #2--B题 (DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。