SSLOJ1471 Y

2022-09-23 01:22:06 字數 674 閱讀 1205

設 \(f[i][j][s]\) 表示 \(i\) 到 \(j\) 之間是否存在狀態為 \(s\) 的路徑。時間複雜度 \(o(2^n\times n^2)\)。

顯然這並不是一個可以接受的複雜度。發現可以 \(\operatorname\),又喜聞樂見的發現這是一個 \(\operatorname\) 陣列,所以直接用 \(\operatorname\) 代替其即可。

然後計算答案的時候,列舉前後兩段的狀態,然後乘法原理即可。

時間複雜度 \(o(\frac}\times n^2}+2^d)\)。

#include using namespace std;

const int n=100,m=(1<<11);

int n,m,d,d1,d2,ans;

bitsetf[m],g[m],dis[2][n];

int main()

for (int i=n;i>=1;i--)

for (int i=0;i

for (int j=0;j

ans+=(f[(1<

printf("%d",ans);

return 0;

}

折半搜尋,狀壓dp nssl 1471 Y

設 dp i j s 表示從 i 到 j 的一條路徑狀態為 s 是否存在 但是這樣肯定會t掉,考慮拼湊路徑,分成兩部分, 設 dp 0 1 s 分別表示以某個起點 終點開始的一條路徑狀態為 s 是否存在, 現在表示一個點集,用出邊的點集轉移,可以用bitset維護, 然後如果 dp 0 s dp 1...