題意 ：

• 其他條件和上題相同
• 這里已知n個點，給定每個點的編號和顏色
• 求這個樹的合法染色方案，取模1e9 + 7

思路 ：

• 首先預處理$d[c][k]$表示根結點顏色為c，深度為k的滿二叉樹的方案
• 0 <= c < 6， 1 <= k <= 60，數據范圍較小，因此可以很快預處理
• 如果一顆子樹，所有點都沒有顏色，那么可以用預處理的數組直接$O(1)$給出方案數
• 因此我們只需要關注有帶色點的子樹
• 由于只有2000個點有顏色，k<=60，因此最多2000*60個點是我們需要關注的
• 我們對這2000*60個點單獨記憶化搜索即可
• $d2[id][c]$表示id點顏色為c，子樹的方案數
• $d[][]$和$d2[][]$的轉移 ：
• 枚舉左右子結點的顏色即可
• 注意思考為什么需要映射

#include <iostream> #include <cstring> #include <map>using namespace std;typedef long long ll;const ll mod = 1e9 + 7;ll n, k; ll lim[10][10]; ll d[10][66]; // 根結點顏色為c，層數為k的滿二叉樹方案數 ll d2[2222 * 66][6]; // i點顏色為j的子樹的方案數 map<ll, ll> col; map<ll, bool> mark; // 標記子樹中至少有一個點已知顏色的點 map<ll, ll> idx; ll num;// 顏色和數字的映射 map<char, ll> c_mp = {{'w', 0},{'y', 1},{'g', 2},{'b', 3},{'r', 4},{'o', 5}, }; /* 0是白 白黃 1是黃 白黃 2是綠 綠藍 3是藍 綠藍 4是紅 紅橙 5是橙 紅橙 */// 對lim數組（兩個顏色不能相鄰）進行初始化 void init() {lim[0][0] = lim[0][1] = 1;lim[1][0] = lim[1][1] = 1;lim[2][3] = lim[2][2] = 1;lim[3][2] = lim[3][3] = 1;lim[4][5] = lim[4][4] = 1;lim[5][4] = lim[5][5] = 1; }// 顏色，層數 ll dp_dfs(ll c, ll k) {if (k == 1) return 1; // 最后一層（注意這種倒過來表示層數的方法if (d[c][k] != -1) return d[c][k]; // 記憶化搜索d[c][k] = 0; // 開始累加方案for (int i = 0; i < 6; i ++ ) // 左兒子{if (lim[c][i]) continue; // 這種顏色方案不合法for (int j = 0; j < 6; j ++ ) // 右兒子{if (lim[c][j]) continue;// 該子樹的根結點顏色為c，且這個根結點位于層數k，子樹的方案// 子樹的方案就是累加左右子樹 相乘 的結果d[c][k] = (d[c][k] + dp_dfs(i, k - 1) * dp_dfs(j, k - 1) % mod) % mod;}}return d[c][k]; // 返回結果 }// 當前根結點的顏色，當前根結點的層數，當前根結點的編號 ll dfs(ll c, ll k, ll id) {if (col.count(id) && col[id] != c) return 0; // 如果當前根結點已知顏色且顏色不是c，則這種方案不合法if (k == 1) return 1; // 最后一層// 如果子樹中所有點都沒有顏色，直接返回預處理的結果if (!mark[id]) return d[c][k];// 如果至少有一個子結點有顏色，則記憶化搜索if (!idx.count(id)) idx[id] = ++ num; // 如果這個點沒有被訪問過，更新映射ll x = idx[id]; // 獲取映射后的下標if (d2[x][c] != -1) return d2[x][c]; // 記憶化搜索d2[x][c] = 0; // 訪問到了這個狀態，開始給這個狀態累加答案ll l = id << 1, r = id << 1 | 1; // 左右兒子，注意這里是用編號，而不是映射for (int i = 0; i < 6; i ++ ){if (lim[c][i]) continue;for (int j = 0; j < 6; j ++ ){if (lim[c][j]) continue;d2[x][c] = (d2[x][c] + dfs(i, k - 1, l) * dfs(j, k - 1, r) % mod) % mod;}}return d2[x][c]; }void solve() {init(); // 初始化不能相鄰的顏色cin >> k >> n;// 初始化，-1表示未曾訪問這種方案（記憶化搜索）memset(d, -1, sizeof d);memset(d2, -1, sizeof d2);// 子樹中沒有一個結點有顏色，for (int i = 0; i < 6; i ++ )dp_dfs(i, k);// n個有顏色的點for (int i = 1; i <= n; i ++ ){ll x; string s;cin >> x >> s;col[x] = c_mp[s[0]]; // id到顏色的映射while (x) // O(logn)標記所有祖先結點，這些祖先結點的子樹都有有顏色的點{mark[x] = 1;x /= 2;}}ll ans = 0;for (int i = 0; i < 6; i ++ )ans = (ans + dfs(i, k, 1)) % mod;// 方案累加，【顏色，層數，編號】cout << ans << endl; }int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _ = 1; // cin >> _;while (_ -- ){solve();}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的E2. Rubik‘s Cube Coloring (hard version) dp，满二叉树（2300）的全部內容，希望文章能夠幫你解決所遇到的問題。

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