CCPC2020長春 J. Abstract Painting（狀壓dp）

J. Abstract Painting（狀壓dp）

題意

給定n，在x軸[0,n]范圍內畫半徑不超過5的圓，圓心在x軸上，要求任意兩個圓不相交（可以相切），且已有固定的k個圓，求滿足條件的畫法方案數，

分析

很明顯從dp的角度思考，一開始考慮區間dp，但是總狀態數 O ( n 2 ) O(n^2) O(n2) ，轉移 O ( n ) O(n) O(n)，總復雜度 O ( n 3 ) O(n^3) O(n3)，超時，

于是從線性dp的角度考慮，發現因為圓的半徑小于等于5，因此某一點的情況只對從這一點往后10個點有后效性，也就是說可以用狀態壓縮的方法記錄前10個點是否在某個圓內 ( 2 10 ) (2^{10}) (210)，同時列舉所有以某點為右界的圓的方案數（ 2 5 2^5 25）進行轉移，狀態數 O ( 2 10 ? n ) O(2^{10}·n) O(210?n)，轉移復雜度 O ( 2 5 ) O(2^5) O(25)，對于已經存在的圓，轉移時要檢查轉移后的方案是否包含了這個圓，如果不包含則不進行轉移，

再結合代碼稍微解釋一下， d p [ i ] [ j ] dp[i][j] dp[i][j]表示計算到第 i i i位，且第 [ i ? 9 , i ] [i - 9, i] [i?9,i]的點被包含情況為 j j j的狀態， j k j_k jk?在二進制上為1和0分別表示第 i ? k i - k i?k位被包含和不被包含（即該點是否能作為某個圓的左界），為了寫起來方便，把坐標整體右移一位，則起始狀態為 d p [ 0 ] [ 1023 ] = 1 dp[0][1023]=1 dp[0][1023]=1（因為x坐標為負的點都不能作為左界）

接著列舉轉移的方案， p o s pos pos陣列記錄了列舉以某點為右界的圓的方案數，其中 p o s [ i ] pos[i] pos[i]用來判斷當前狀態是否能進行轉移， m a s k [ i ] mask[i] mask[i]根據半徑最大的圓修改當前狀態，

代碼

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '
#define debugl(x) cerr << #x << " = " << x << '\n'

using namespace std;
typedef long long ll;

const int N = 1e3 + 5, M = 1200, MOD = 1e9 + 7, MK = 1023;

int n, k;

ll dp[N][M];

int pos[40], mask[40];

vector<int> fix[N];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        int c, r; scanf("%d %d", &c, &r);
        c++;
        fix[c + r].push_back(r * 2);
    }
    memset(mask, -1, sizeof(mask));
    for (int i = 1; i <= 31; i++) {
        int tmp = 0;
        for (int j = 4; j >= 0; j--) {
            tmp = (tmp * 2 + ((i >> j) & 1)) * 2;
            if (mask[i] == -1 && ((i >> j) & 1)) mask[i] = (1 << (j * 2 + 1)) - 1;
        }
        pos[i] = tmp;
    }
    dp[0][MK] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= MK; j++) {
            if (fix[i + 1].size() == 0) {
                dp[i + 1][(j << 1) & MK] += dp[i][j];
                dp[i + 1][(j << 1) & MK] %= MOD;
            }
            for (int k = 1; k <= 31; k++) {
                bool cont = 0;
                for (int to : fix[i + 1]) {
                    if (!((pos[k] >> (to - 1)) & 1)) cont = 1;
                    if (cont) break;
                }
                if (cont || (j & pos[k]) != 0) continue;
                dp[i + 1][(((j | mask[k]) << 1)) & MK] += dp[i][j];
                dp[i + 1][(((j | mask[k]) << 1)) & MK] %= MOD;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i <= MK; i++) {
        ans += dp[n + 1][i];
        ans %= MOD;
    }
    cout << ans;
    return 0;
}