https://ac.nowcoder.com/acm/contest/330/D

C++版本一

std

題解：

狀態壓縮，輪廓線DP

好多6x6被騙去寫暴搜的.jpg。實際上6x6全是?的答案高達1e18.

解法一：By 野雞驗題人
用 dp[x][state] 表示考慮到第 x 行，該行填寫的數字的十進制狀態為state的方案數。
這樣的復雜度有點大，但是由于題目中的要求和為素數存在很強的限制，因此可以先預處理出所有符合條件的一行的state以及每個state可以轉移的狀態。加上本題寬松的時限，足以通過。
當然第一維是可以滾動掉的（然而并沒有什么卵用）。

解法二：標程
用 dp[x][state] 表示考慮到第 x 個格子，它所在的輪廓線上所有數字的十進制狀態為state的方案數。其中state的最高位存它前一行的那一格，最低為存它前一列的那一格。
如圖所示，這樣狀態的轉移就是一個“帶溢出的十進制左移并補上填的數字“。
當然第一維是可以滾動掉的。

#include <bits/stdc++.h> using namespace std; char maze[10][10]; bool isprime[21] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0}; long long dp[1000000 + 7][2];int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++)scanf("%s", maze[i]);int top = 1;for (int i = 1; i < m; i++)top *= 10;dp[0][0] = 1;int v = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){for (int k = 0; k < top * 10; k++){if (dp[k][v]){for (int add = 0; add < 10; add++){if ((maze[i][j] == '?' || maze[i][j] == add + '0') && (!i || isprime[add + k / top]) && (!j || isprime[add + k % 10])){dp[k % top * 10 + add][v ^ 1] += dp[k][v];}}dp[k][v] = 0;}}v ^= 1;}}long long ans = 0;for (int i = 0; i < top * 10; i++)ans += dp[i][v];printf("%lld\n", ans); }

?

總結

以上是生活随笔為你收集整理的Applese 填数字的全部內容，希望文章能夠幫你解決所遇到的問題。

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