插頭DP && 概率DP / 期望DP
- 寫在前面：
- 插頭DP
- P5056 【模板】插頭dp
- 手寫哈希表的方法：
- 拉鏈法的代碼如下：
- 開放尋址法的代碼如下：
- 接下來是這道題的代碼實作：
- P3190 [HNOI2007]神奇游樂園
- 具體的代碼實作如下:
- P3272 [SCOI2011]地板
- 具體的代碼實作如下：
- 期望DP
- UVA12230 過河 Crossing Rivers
- 具體的代碼實作如下：
- 期望dp / 概率dp的概念：
- 期望DP / 概率DP常見的狀態表示及其轉移：
- SP1026 FAVDICE - Favorite Dice
- 具體的代碼實作如下：
- 【SGU495】【Kids and Prizes】
- 具體的代碼實作如下：
- CF148D Bag of mice
- 具體的代碼實作如下：
- POJ 3071 Football
- 具體的代碼實作如下：
- CodeForces 768 D - Jon and Orbs
- 具體的代碼實作如下：
- POJ2096 Collecting Bugs
- 具體的代碼實作如下：
- P1850 [NOIP2016 提高組] 換教室
- 具體的代碼實作如下：
- HDU3853 LOOPS
- 具體的代碼實作如下：
- 總結：
寫在前面：
??快開學了，先發下最近整理的DP，還有過年前學的狀壓DP、記憶化搜索等基礎DP還有圖論等知識還在整理中…
??由于本人平時比較懶，所以把十幾道題都弄在一篇博客，這篇博客比較長，近3萬字，但我相信大家還是能看懂我在說什么的，
插頭DP
P5056 【模板】插頭dp
??有些狀壓DP問題要求我們記錄狀態的連通性資訊，這類問題一般被形象的稱為插頭DP或連通性狀態壓縮DP，插頭dp是基于連通性狀態壓縮的動態規劃，一般的適用范圍：資料范圍小，并且處于網格圖中，對連通性有要求（要求選擇出來的格子是一個連通塊或者是一個路徑/回路），這樣說起來很抽象，我先介紹一道插頭dp的模板題：
??給我們一個n * m的棋盤，這個棋盤里面有些格子是障礙，有些格子是空格，求這個棋盤有多少個不同的哈密頓回路（要經過每個格子，并且每個格子只能經過一遍），我們來簡單回顧一下哈密頓回路的做法：先用一個狀態S表示我們當前已經走過哪些點，另外用i表示我們當前走到了哪個點，然后列舉下一個點是哪一個點，假設下一個點是j，f(s, i)就變成了f(s | 1 << j, j)，此時的時間復雜度是2n * n2，現在是一個棋盤，如果按照這種做法來做時間復雜度會太大，棋盤有個特點：每個格子只能和上下左右四個格子相連，并不是能和任意格子相連，所以可以按照一行一行來列舉所有狀態（對于一般圖我們就不能這樣），我們遞推的時候一般是按格來遞推，舉個例子，我們要考慮這個格子，這也意味著我們已經考慮完了這個紅色線上方的格子，所以此時我們只要分析這個格子的狀態就可以了，
??因為我們要組成一個回路，所以每個格子只能有兩條邊會被經過，假設有一個邊是進來的，有一個邊是出去的，也就是在它的四條邊里邊選兩條邊經過，這樣經過每個格子有6種情況，對于整一個連通塊，我們只關心它輪廓線上的狀態（即每條邊有沒有線經過），還要維護輪廓線上方部分的連通性（經過輪廓線的邊哪些是屬于同個連通塊的）
??（上面0和7，3和6就是屬于同一個連通塊）記錄連通塊一般有兩種方法：1、最小表示法，從左往右遍歷輪廓線，當遍歷到沒被標記的邊（且有路徑要經過它）的時候，按順序標記，所以0和7標記成1，3和6標記成2（屬于同個連通塊標記相同），所以此時輪廓線的狀態：10020021，2、括號表示法，括號表示法的適用范圍要小一些，但效率更高（首選），因為我們要找的是一個哈密頓回路，這就意味著上半部分有一條邊上去，就一定有一條邊下來，這些邊必然是兩兩配對的，而且這兩條邊之間的連通塊是不可能交叉的（兩條邊所連的路徑不可能交叉），因為是相鄰的兩兩配對，所以可以看做是若干個括號，我們用1表示“左括號”，用2表示有括號，用一個三進制的數就能表示輪廓線的狀態，所以此時輪廓線的狀態：10010022，
??這道題用括號表示法比用最小表示法的優勢是，我們用012就可以表示輪廓線的狀態，而最小表示法要用到的數可能很大（有多少個連通塊，最大就是多少），另外，括號表示法每一位就012，可以把它看成是4進制，然后在更新狀態的時候就可以用位運算去優化，
??狀態表示是三維，f[i, j, s]表示當遍歷到第i行第j列的格子的時候分界線的狀態是s時，所有方案的數量，s有效的狀態是4、5萬個（因為它要滿足1和2是兩兩配對的），插頭dp比較麻煩的就是狀態轉移，我們把目標格子(g[i, j])在輪廓線上的邊標記成x和y，輪廓線上的狀態為state，需要分成以下幾種情況（轉移的程序中x對應格子下面的邊，y對應格子右邊的邊）：
??1、g[i, j]是障礙物，x和y一定是0，且這個格子也不會有路徑經過，所以state不變(x和y都是0，轉移之后也是0)
接下來g[i, j]不是障礙物的情況：
??2、x和y均為0，更新后state中x = 1, y = 2
??3、x為0，y非0，更新后state中狀態不變或者x = y, y = 0
??4、x非0，y為0，更新后state中y = x, x = 0或者狀態不變
??5、x = y = 1，x和y相連，此時state中原來x和y的位置變成0，然后離y最近的2變成1，又因為格子已經有兩條邊了，所以更新之后x和y對應的位置為0，
??6、x = y = 2，x和y相連，此時state中原來x和y的位置變成0，然后離x最近的1變成2，又因為格子已經有兩條邊了，所以更新之后x和y對應的位置為0，
??7、x = 2, y = 1，x與其前面第一個1配對，y與后面第一個2配對，更新后state中x = 0, y = 0，
??8、x = 1, y = 2，x是某個路徑的左半邊，y是某個路徑的右半邊，又因為x和y在輪廓線中是相鄰的，所以x和y是屬于同一個路徑的，這種情況只會發生在最后一個合法的格子，
??接下來分析資料，在f[i, j, s]中s是輪廓線的狀態，因為我們是用四進制來表示三進制，而4的13次方是等于67108864，而有效的狀態只有4w多個，所以插頭dp在存狀態的時候一般是用哈希表來存的，而且哈希表最好不要用stl中的哈希表，因為插頭dp的常數比較大，題目卡得比較嚴，所以現在我們要手寫哈希表…
手寫哈希表的方法：
??1、開放尋址法
??2、拉鏈法
??哈希表的作用：從較龐大的空間/值域，把它映射到一個較小的空間(0 ~ N)，
??結合這道題來介紹手寫哈希表的兩種做法：
??當要存盤的數是x時，我們可以構造一個哈希函式h(x)，這個函式它可以把-109 ~ 109的一個數映射到0 ~ 105之間的一個數，通常會采取x % 105的做法，值域比較大，但是映射的結果比較小，所以必然會產生沖突，也就是我們可能會把兩個相同的數映射成同一個數，對于沖突的解決方式可以采用兩種方法(開放尋址法/拉鏈法)，
??拉鏈法：
??先開一個長度為105的陣列，當兩個數發生沖突的時候，就在某個位置i拉下一條鏈，把之前的數放在鏈的第一個位置，然后把新得到的數放在i位置，類似于對于某一個陣列元素接一個鄰接表，哈希演算法是一種期望演算法，雖然說每一個位置都有可能拉下來一條鏈，但是在平均情況下，每一條鏈的長度可以看成是常數，所以哈希表的時間復雜度可以看成O(1)，
??我們在建立一個哈希表的長度的時候一般取成一個質數（就是取模的數），而且這個質數要離2的n次方盡可能遠，定義h[N]哈希陣列，對于每一個“槽”，我們要向下拉一條鏈（類似于之前的鏈表），鏈表要存兩個東西，一個是它的值e[idx]，另一個是下一個值的下標ne[idx]，具體做法和對鏈表的插入查找相同，
拉鏈法的代碼如下：
const int N = 100003;
int h[N], e[N], ne[N], idx;
int insert(int x){
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
int find(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i]){
if(e[i] == x) return 1;
}
return 0;
}
int main(){
int n, m;
cin >> n;
char p[2];
memset(h, -1, sizeof(h));
while(n--){
scanf("%s%d", p, &m);
if(p[0] == 'I') insert(m);
else{
if(find(m)) cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}
??開放尋址法：
??它只開了一個一維陣列，一維陣列的長度一般要開到題目資料范圍的兩到三倍(這道題開到20w ~ 30w)，這樣的話沖突的概率就小一點，開放尋址法就像我們去廁所找坑位，我想要的坑位有人了，就按順序看看下一個空位有沒有人，以此類推，直到找到坑位為止，
開放尋址法的代碼如下：
const int N = 200003, null = 0x3f3f3f3f;
int find(int x){
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x){
k++;
if(k == N) k = 0;
}
return k;
}
int main(){
int n, m;
cin >> n;
char p[2];
memset(h, 0x3f, sizeof(h));
while(n--){
scanf("%s%d", p, &m);
if(p[0] == 'I') h[find(m)] = m;
else{
if(h[find(m)] == null) cout << "No\n";
else cout << "Yes\n";
}
}
return 0;
}
??言歸正傳，我在插頭dp這道題用開放尋址法，另外，這個題目合法狀態大約4w多個，估算一下5w * 144（格子數），大概是700多w個狀態，有些題目的數量可能更多，所以要用到滾動陣列，由于對于每個格子，總共的狀態有6k多w個，合法狀態只有不到5w個，我們去列舉的時候就沒必要去列舉所有狀態，而要用一個陣列先存盤每一次滾動的有效狀態，估算下時間復雜度：f[i, j, s]假設所有有效狀態數量是S(最多不到5w)，再乘以i、j(n2)，然后再算狀態的時候，對于5和6的情況，我們是需要列舉找出與某條邊配對的邊，最壞情況下是需要O(N)的計算量，所以整個演算法的時間復雜度就是S * n3，大概是5w * 12 * 12 * 12 = 8.64 * 107，但本質上來說沒有這么高（有效狀態不到5w，也不是所有狀態都要列舉8種情況），這就是插頭dp的具體思路，
接下來是這道題的代碼實作：
??（具體有點復雜，為了大家方便理解，我每一行我都加了注釋，雖然我自己都覺得有點惡心…）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
void debug_out(){
cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef local
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif
using namespace std;
const int N = 50005, M = N * 2 + 7;
//狀態數量，3^13 ~ 6000萬個，有效的大概為4萬~5萬個
//開放尋址法的陣列通常是2~3倍，同時取成質數，用于取模
int g[15][15], q[2][N], cnt[2], h[2][M], ex, ey;
//g是判斷是不是障礙物
//q是滾動陣列，存盤的是某個有效狀態對應在哈希表的下標
//h是滾動陣列，滾動hash表，第二維是哈希值的位置，存盤的是哈希表某個下標對應的具體有效狀態（哈希值）
//cnt陣列是每一次滾動程序中（當前格子）有效狀態的數量
LL v[2][M], ans;
//v是有效狀態對應的方案數，ans累加所有方案數
int set(int k, int v){ //構造四進制的第k位數字為v的數字
return v * (1 << k * 2);
}
int get(int state, int k){ //求第k個格子的狀態,四進制的第k位數字
return state >> (k * 2) & 3;
}
int find(int cur, int x){ //開放尋址法找到給有效狀態存盤的哈希表下標
int t = x % M; //取模找到預定存盤的位置
while(h[cur][t] != -1 && h[cur][t] != x){ //直到找到空位置或者發現已經存過了
if(++t == M) t = 0; //在按順序尋找空位置的程序中，要是到了陣列的右邊界，就回到陣列的頭部再找
}
return t; //回傳有效狀態存盤的哈希表下標
}
int insert(int cur, int state, LL w){ //在滾動哈希表中新加入有效狀態
int t = find(cur, state); //給有效狀態找存盤下標
if(h[cur][t] == -1){ //這個有效狀態之前沒存過
q[cur][++cnt[cur]] = t; //儲存它的下標 cnt更新當前格子的有效狀態數
h[cur][t] = state; //儲存具體的有效狀態
v[cur][t] = w; //儲存符合當前有效狀態的所有方案數
}
else v[cur][t] += w; //這個有效狀態之前存過，把它的合法方案數累加
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){ //讀入n * m的矩陣
char a[15];
scanf("%s", a + 1);
for(int j = 1; j <= m; j++){
if(a[j] == '.'){
g[i][j] = 1; //不是障礙標為1，是障礙標為0
ex = i, ey = j; //記錄最后一個有效格子，我們要在最后一個有效格子記錄所有方案
}
}
}
memset(h, -1, sizeof(h)); //初始化滾動哈希表（"兩個"哈希表的元素值均為-1）
int cur = 0;
insert(cur, 0, 1); //最初的分界線，對應的方案數為1
for(int i = 1; i <= n; i++){ //列舉所有行
for(int j = 1; j <= cnt[cur]; j++){ //更新下一行新的分界線狀態，從輪廓線是 一條直線和上方最右邊格子的最右邊 轉換到 一條直線和下方最左邊格子的最左邊
h[cur][q[cur][j]] <<= 2; //新的一行所有有效狀態都整體右移一位（用<<的原因是所有有效狀態是從右往左記錄的）
}
for(int j = 1; j <= m; j++){ //列舉所有格子
int l = cur; //保存之前的狀態（h[l][q[l][k]]是之前格子轉移后的有效狀態，v[l][q[l][k]]是之前格子轉移后的方案數）
cur ^= 1; //cur ^= 1，更新為當前格子
cnt[cur] = 0; //當前格子轉移后的有效狀態數量初始化為0
memset(h[cur], -1, sizeof(h[cur])); //清空滾動哈希表中記錄當前的有效狀態
for(int k = 1; k <= cnt[l]; k++){ //遍歷從上一個格子轉移之后得到的所有有效狀態
int state = h[l][q[l][k]]; //state是具體的有效狀態，便于后續對狀態中某一特定位上的數進行修改
LL w = v[l][q[l][k]]; //w是符合這個有效狀態的所有方案數
int x = get(state, j - 1), y = get(state, j); //x和y的具體位置跟之前圖示的x和y相同
//下面是上面圖示的所有情況
if(g[i][j] == 0){ //第一種情況
if(!x && !y){
insert(cur, state, w);
}
}
else if(!x && !y){ //第二種情況
if(g[i + 1][j] && g[i][j + 1]) insert(cur, state + set(j - 1, 1) + set(j, 2), w);
}
else if(!x && y){ //第三種情況
if(g[i + 1][j]) insert(cur, state + set(j - 1, y) - set(j, y), w);
if(g[i][j + 1]) insert(cur, state, w);
}
else if(x && !y){ //第四種情況
if(g[i][j + 1]) insert(cur, state + set(j, x) - set(j - 1, x), w);
if(g[i + 1][j]) insert(cur, state, w);
}
else if(x == 1 && y == 1){ //第五種情況
for(int s = 1, u = j + 1;;u++){
int p = get(state, u);
if(p == 1) s++;
else if(p == 2){ //找到匹配的右括號
if(--s == 0){
insert(cur, state - set(j - 1, 1) - set(j, 1) - set(u, 1), w);
break;
}
}
}
}
else if(x == 2 && y == 2){ //第六種情況
for(int s = 1, u = j - 2;; u--){
int p = get(state, u);
if(p == 2) s++;
else if(p == 1){ //找到匹配的左括號
if(--s == 0){
insert(cur, state - set(j - 1, 2) - set(j, 2) + set(u, 1), w);
break;
}
}
}
}
else if(x == 2 && y == 1){ //第七種情況
insert(cur, state - set(j - 1, 2) - set(j, 1), w);
}
else if(i == ex && j == ey){ //第八種情況（已經到了最后一個非障礙格子）
ans += w; //累加所有合法方案數
}
}
}
}
cout << ans << '\n';
return 0;
}
P3190 [HNOI2007]神奇游樂園
??這道題相當于一個n * m的棋盤，然后從里邊選擇一個回路，但這道題跟上一題不一樣的地方是不一定每一個格子都要經過，回路里邊包含的格子數量不能少于四，也就是起碼要存在一個拐點，要我們求在所有的回路里權值和最大是多少，狀態表示和上面那道題是類似的，只有狀態轉移不太一樣，我們用f[i, j, S]遍歷到當前第i行j列的格子輪廓線的狀態是S時所有方案的集合，S在存插頭狀態的時候，跟上面那道題是類似的，也是用三進制（類似于括號序列的方式）來存下每條邊的狀態，主要是維護下所有插頭的連通性，
??狀態轉移是7種情況（上一道題格子可能是障礙物），我就不畫圖了，用文字說明（每個變數表示的東西都跟上一道題一樣）：
??情況一：x = 0, y = 0, 這個格子有兩種可能（因為這個格子可以走，可以不走），不走的話，insert(cur, state, w);；走的話，insert(cur, state + set(j - 1, 1) + set(j, 2), w + g[i][j]);
??情況二：x = 0, y非0，經過這個格子的時候如果向右走，insert(cur, state, w + g[i][j]);
如果向下走，insert(cur, state + set(j - 1, y) - set(j, y), w + g[i][j]);
??情況三：x非0, y = 0，經過這個格子的時候如果向右走，insert(cur, state + set(j, x) - set(j - 1, x), w + g[i][j]);如果向下走，insert(cur, state, w + g[i][j]);
??情況四：如果x = 1, y = 1，在y的右邊找到第一個2與y配對，把其更新為1，insert(cur, state -set(j - 1, 1) - set(j, 1) - set(u, 1), w + g[i][j]);
??情況五：如果x = 2, y = 2，在x的左邊找到第一個1與x配對，把其更新為2，insert(cur, state - set(j - 1, 2) - set(j, 2) + set(u, 1), w + g[i][j]);
??情況六：x = 2, y = 1，這種狀態其它邊不受影響，直接轉移就好了insert(cur, state - set(j - 1, 2) - set(j, 1), w + g[i][j]);
??情況七：x = 1, y = 2，這種狀態說明輪廓線的上方已經形成了回路，因為這道題不是所有的格子都要走，所以當遇到這種情況的時候，我們要更新權值和的最大值：ans = max(ans, w + g[i][j]);
具體的代碼實作如下:
??（跟第一道題很像，只是狀態轉移的條件和程序不一樣，其他輔助函式都一樣）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
void debug_out(){
cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef local
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif
using namespace std;
const int N = 130, M = N * 2 + 7;
int g[N][N], h[2][M], q[2][N], cnt[2];
LL v[2][M], ans = -1e9;
int set(int k, int v){
return v * (1 << k * 2);
}
int get(int state, int k){
return state >> k * 2 & 3;
}
int find(int cur, LL x){
int t = x % M;
while(h[cur][t] != -1 && h[cur][t] != x){
if(++t == M) t = 0;
}
return t;
}
int insert(int cur, int x, LL w){
int t = find(cur, x);
if(h[cur][t] == -1){
q[cur][++cnt[cur]] = t;
h[cur][t] = x;
v[cur][t] = w;
}
else v[cur][t] = max(v[cur][t], w);
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> g[i][j];
}
}
memset(h, -1, sizeof h);
int cur = 0;
insert(cur, 0, 0);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= cnt[cur]; j++){
h[cur][q[cur][j]] <<= 2;
}
for(int j = 1; j <= m; j++){
int l = cur;
cur ^= 1;
cnt[cur] = 0;
memset(h[cur], -1, sizeof(h[cur]));
for(int k = 1; k <= cnt[l]; k++){
int state = h[l][q[l][k]];
LL w = v[l][q[l][k]];
int x = get(state, j - 1), y = get(state, j);
if(!x && !y){
if(i < n && j < m) insert(cur, state + set(j - 1, 1) + set(j, 2), w + g[i][j]);
insert(cur, state, w);
}
else if(!x && y){
if(i < n) insert(cur, state + set(j - 1, y) - set(j, y), w + g[i][j]);
if(j < m) insert(cur, state, w + g[i][j]);
}
else if(x && !y){
if(i < n) insert(cur, state, w + g[i][j]);
if(j < m) insert(cur, state + set(j, x) - set(j - 1, x), w + g[i][j]);
}
else if(x == 1 && y == 1){
for(int u = j + 1, s = 1;; u++){
int p = get(state, u);
if(p == 1) s++;
else if(p == 2){
if(--s == 0){
insert(cur, state -set(j - 1, 1) - set(j, 1) - set(u, 1), w + g[i][j]);
break;
}
}
}
}
else if(x == 2 && y == 2){
for(int u = j - 2, s = 1;; u--){
int p = get(state, u);
if(p == 2) s++;
else if(p == 1){
if(--s == 0){
insert(cur, state - set(j - 1, 2) - set(j, 2) + set(u, 1), w + g[i][j]);
break;
}
}
}
}
else if(x == 2 && y == 1){
insert(cur, state - set(j - 1, 2) - set(j, 1), w + g[i][j]);
}
else ans = max(ans, w + g[i][j]);
}
}
}
cout << ans << '\n';
return 0;
}
P3272 [SCOI2011]地板
??這道題是一個非回路的問題，在r * c的地面上鋪地板，地面上可能有障礙物，沒有障礙物的地方一定要鋪上地板，而且鋪的地板要呈”L”型（如題目圖示），求鋪滿整個地面的總方案數，題目中r和c沒有大小關系，但規定了r * c <= 100，因此r和c的最小值一定是小于等于10，從資料范圍上看它也是可以用插頭dp的，這一題跟上兩道題不一樣，它不是一個回路，就不可以用類似括號序列的方式來表示輪廓線的狀態，這道題依舊用f[i, j, S]來表示遍歷到第i行第j列的格子，輪廓線的狀態是S時的方案數，這道題輪廓線上的插頭狀態
存的是”L”型地板經過輪廓線上的某一條邊時，在輪廓線上方是否已經“拐彎”，它存的是每個插頭當前有沒有“拐彎”，如果無插頭，記錄為0；如果有插頭且還沒“拐彎”，記錄為1；如果有插頭且已經“拐彎”，記錄為2，重點是如何進行狀態轉移，可以分成7種情況（（每個變數表示的東西都跟上一道題一樣）：
??情況一：如果這個格子是障礙物，insert(cur, state, w);
??情況二：當格子不是障礙物時（下面的情況都是格子不是障礙物的情況），x = 0, y = 0，還可以分成三種子情況，以當前格子為起點，如果只往下走，insert(cur, state + set(j - 1, 1), w);如果只往右走，insert(cur, state + set(j, 1), w);如果既往下又往右走，insert(cur, state + set(j - 1, 2) + set(j, 2), w);
??情況三：x = 0, y = 1，如果往下走，insert(cur, state + set(j - 1, 1) - set(j, 1), w);如果往右走insert(cur, state + set(j, 1), w);
??情況四：x = 0, y = 2，如果往下走，insert(cur, state - set(j, 2) + set(j - 1, 2), w);如果在當前格子停下insert(cur, state - set(j, 2), w);如果已經遍歷到最后一個有效格子，更新方案數，ans = (ans + w) % mod;
??情況五：x = 1, y = 0，如果往右走，insert(cur, state - set(j - 1, 1) + set(j , 1) ,w);如果往下走，insert(cur, state + set(j - 1, 1), w);
??情況六：x = 2, y = 0，如果往右走，insert(cur, state - set(j - 1, 2) + set(j , 2), w);如果在當前格子停下insert(cur, state - set(j - 1, 2), w);如果已經遍歷到最后一個有效格子，更新方案數，ans = (ans + w) % mod;
??情況七：x = 1, y = 1，這種情況說明這個格子是某個“L”型地板的“拐彎”處，insert(cur, state - set(j - 1, 1) - set(j, 1), w);如果此時已經遍歷到了最后一個有效的格子，更新方案數，ans = (ans + w) % mod;
??注意，這道題在進行狀態轉移的時候要考慮當前“L”型地板覆寫的地方有沒有障礙物，
具體的代碼實作如下：
??（跟前兩道插頭dp很像，只是狀態轉移的條件和程序不一樣，其他輔助函式都一樣）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
void debug_out(){
cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef local
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif
const int N = 180000, M = N * 2 + 7, mod = 20110520;
int ex, ey, h[2][M], q[2][N], v[2][M], ans, cnt[2], g[105][105];
int set(int k, int v){
return v * (1 << k * 2);
}
int get(int state, int k){
return state >> k * 2 & 3;
}
int find(int cur, int x){
int t = x % M;
while(h[cur][t] != -1 && h[cur][t] != x){
if(++t == M) t = 0;
}
return t;
}
int insert(int cur, int state, int w){
int t = find(cur, state);
if(h[cur][t] == -1){
q[cur][++cnt[cur]] = t;
h[cur][t] = state;
v[cur][t] = w;
}
else v[cur][t] = (v[cur][t] + w) % mod;
return 0;
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
int n, m;
char a[105];
cin >> n >> m;
for(int i = 1; i <= n; i++){
scanf("%s", a + 1);
for(int j = 1; j <= m; j++){
if(a[j] == '_'){
g[i][j] = 1;
ex = i, ey = j;
}
}
}
if(n < m){
swap(n, m), swap(ex, ey);
for(int i = 1; i <= n; i++){
for(int j = 1; j < i; j++){
swap(g[i][j], g[j][i]);
}
}
}
memset(h, -1, sizeof(h));
int cur = 0;
insert(cur, 0, 1);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= cnt[cur]; j++){
h[cur][q[cur][j]] <<= 2;
}
for(int j = 1; j <= m; j++){
int l = cur;
cur ^= 1, cnt[cur] = 0;
memset(h[cur], -1, sizeof h[cur]);
for(int k = 1; k <= cnt[l]; k++){
int state = h[l][q[l][k]], w = v[l][q[l][k]];
int x = get(state, j - 1), y = get(state, j);
if(!g[i][j]){
if(!x && !y) insert(cur, state, w);
}
else if(!x && !y){
if(g[i][j + 1]) insert(cur, state + set(j, 1), w);
if(g[i + 1][j]) insert(cur, state + set(j - 1, 1), w);
if(g[i][j + 1] && g[i + 1][j]) insert(cur, state + set(j - 1, 2) + set(j, 2), w);
}
else if(!x && y == 1){
if(g[i][j + 1]) insert(cur, state + set(j, 1), w);
if(g[i + 1][j]) insert(cur, state + set(j - 1, 1) - set(j, 1), w);
}
else if(!x && y == 2){
if(i == ex && j == ey) ans = (ans + w) % mod;
else if(g[i + 1][j]) insert(cur, state - set(j, 2) + set(j - 1, 2), w);
insert(cur, state - set(j, 2), w);
}
else if(x == 1 && !y){
if(g[i][j + 1]) insert(cur, state - set(j - 1, 1) + set(j , 1) ,w);
if(g[i + 1][j]) insert(cur, state + set(j - 1, 1), w);
}
else if(x == 2 && !y){
if(i == ex && j == ey) ans = (ans + w) % mod;
else if(g[i][j + 1]) insert(cur, state - set(j - 1, 2) + set(j , 2), w);
insert(cur, state - set(j - 1, 2), w);
}
else if(x == 1 && y == 1){
if(i == ex && j == ey) ans = (ans + w) % mod;
insert(cur, state - set(j - 1, 1) - set(j, 1), w);
}
}
}
}
cout << ans << '\n';
return 0;
}
期望DP
??在介紹期望dp之前，先做一道簡單的數學求期望，熟悉一下演算法題是怎樣考查期望的，
UVA12230 過河 Crossing Rivers
??題意：從A到B需要經過n條河，已知AB間距離D和每條河的長度L以及在該條河上的船速v，求A到B平均情況下需多長時間，
??陸地行走速度為1，船的位置和朝向均勻隨機，因為在某條河里面船的位置和朝向是均勻隨機的，人在河邊最久等待2 * l / v（人到河邊，船剛走），最理想情況是不用等待，所以平均等待時間的期望就是l / v，加上人坐船過河需要時間，所以人過河（包括等船）需要時間的期望為2 * l / v，一直人在陸地上的速度為1，所以每遇到河時，需要的期望時間就是在總路程長度中，減去河的長度（- l），再加上人過這條河需要時間的期望（+ 2 * l / v），
具體的代碼實作如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, s = 1;
double d, p, l, v;
while(cin >> n >> d){
if(n == 0 && d == 0) break;
while(n--){
cin >> p >> l >> v;
d = d - l + 2 * l / v;
debug(n, d);
}
printf("Case %d: %.3lf\n\n", s++, d);
}
return 0;
}
期望dp / 概率dp的概念：
??根據概率分析，遞推求出每個狀態的期望的演算法，
期望DP / 概率DP常見的狀態表示及其轉移：
??1、設成dp[i]表示已經完成i個，要達到目標狀態的期望，也就是由i狀態變成目標狀態的期望，對于這種方法，轉移的時候要選擇刷表法倒序列舉，（根據這個狀態本身就可以理解）
??2、設成dp[i]表示已經完成i個的期望，對于這種方法，轉移的時候要選擇填表法正序列舉，
??對于以上兩種方法，很多時候可以互換，但是有些時候不能互換，需要經過具體情況靈活判斷，
??3、設成dp[i][j]表示i種物品選擇了j個的期望，
??4、設成dp[i][j]表示有i個第一種物品，j個第二種物品的期望，
??對于以上兩種方法，就是二維的狀態轉移，
??然后就是轉移的具體程序，對于狀態轉移，一般我們要把整個程序拆解成兩種情況：已處理和未處理，也就是符合需要和不符合需要，比如拋硬幣，要算正面朝上的期望，那么就把拋硬幣的程序拆成：朝上和不朝上，或者擲一個有N面的骰子，要算擲多少次才能都擲完各面的期望，那么就把這個擲骰子的程序拆成：擲到已經處理的面和擲到未處理的面，
??這樣的話，就可以通過兩種程序的概率以及上面所講述的期望的性質進行轉移，
??對于填表、刷表法的選擇：一般來講，初始狀態確定時用順推填表，終止狀態確定時可用逆推刷表，
SP1026 FAVDICE - Favorite Dice
??一個n面的骰子，求期望擲幾次能使得每一面都被擲到，dp[i]表示已經從n個面中擲出來i面后，擲出所有面的次數期望，所以dp[n] = 0, dp[0]即為所求，我們可以采用逆推刷表，已知在n面的骰子中已經擲出了i面，再擲一次恰好是沒擲出的面的概率為(n - i) / n，所以從n面的骰子中擲出之前沒擲出的面的期望次數是n / (n - i)，因為是逆推刷表，所以狀態轉移方程：dp[i] = dp[i + 1] + n * 1.0 / (n - i); dp[0]即為所求的期望次數，
具體的代碼實作如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
double dp[1005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, t, s = 1;
cin >> t;
while(t--){
cin >> n;
dp[n] = 0;
for(int i = n - 1; i >= 0; i--){
dp[i] = dp[i + 1] + n * 1.0 / (n - i);
}
printf("%.2lf\n", dp[0]);
}
return 0;
}
【SGU495】【Kids and Prizes】
??這道題是我在網上找的期望dp的基礎題，做完后想提交，才發現SGU這個oj沒了…
??題意：有n個獎品放在n個盒子里，有m個小朋友輪流去選擇一個盒子，若有獎品則拿走，無論有沒有獎品都要將空盒子放回去，問最后獲得獎品個數的期望，
??求獲得獎品個數的期望，只要把每一個小朋友拿到獎品的概率相加即為所求，所以我們要dp求每一輪小朋友拿到獎品的概率，第一個小朋友拿到獎品的概率為1，dp[1] = 1；之后第i個小朋友拿到獎品的概率（dp[i]）與第i - 1個小朋友拿到獎品（dp[i - 1]）的概率有關，分為兩種情況：當第i - 1個小朋友沒有拿到獎品時，此時第i個小朋友拿到獎品的概率與第i - 1個小朋友拿到獎品的概率相同，此時dp[i] = (1 - dp[i - 1]) * dp[i -1]；當第i - 1個小朋友拿到獎品時，第i個小朋友拿到獎品的概率是(dp[i - 1] - 1.0 / n)，此時dp[i] = dp[i - 1] * (dp[i - 1] - 1.0 / n)，結合起來，狀態轉移方程：dp[i] = (1 - dp[i - 1]) * dp[i - 1] + dp[i - 1] * (dp[i - 1] - 1 / n)，
具體的代碼實作如下：
#include <bits/stdc++.h>
using namespace std;
int n,m;
double dp[100005], ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while(~scanf("%d %d",&n,&m)){
dp[1] = 1.0;
for(int i = 2; i <= m; i++){
dp[i] = (1 - dp[i - 1]) * dp[i - 1] + dp[i - 1] * (dp[i - 1] - 1.0 / n);
}
for(int i = 1; i <= m; i++){
ans += dp[i];
}
printf("%.10lf\n", ans);
}
return 0;
}
CF148D Bag of mice
??cf的英文題，我大概說下題意：袋子里有 w 只白鼠和 b 只黑鼠，公主和龍輪流從袋子里抓老鼠，誰先抓到白色老鼠誰就贏，如果袋子里沒有老鼠了并且沒有誰抓到白色老鼠，那么算龍贏，公主每次抓一只老鼠，龍每次抓完一只老鼠之后會有一只老鼠跑出來，每次抓的老鼠和跑出來的老鼠都是隨機的，公主先抓，問公主贏的概率，
??設f[i, j]為輪到公主時袋子里有i只白鼠，j只黑鼠，公主贏的概率，初始化邊界，f[0,j] = 0因為沒有白鼠了算龍贏，f[i, 0] = 1因為抓一只就是白鼠，公主贏，考慮f[i, j]的轉移（每一輪公主和龍輪流拿，可以分成四種情況）：
??情況一：公主抓到了一只白鼠，公主贏了（龍不用抓了），這種情況發生的概率為：i / (i + j)，
??情況二：公主抓到了一只黑鼠，龍抓到了一只白鼠（龍勝利了），這種情況發生的概率為：j / (i + j) * i / (i + j -1)，
??情況三：公主抓到了一只黑鼠，龍抓到了一只黑鼠，跑出來了一只白鼠，轉移到了f[i - 1, j - 2]，這種情況發生的概率：j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2)，
??情況四：公主抓到了一只黑鼠，龍抓到了一只黑鼠，跑出來了一只黑鼠，轉移到了f[i, j - 3]，這種情況發生的概率：j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2)，
??考慮公主贏的概率，第二種情況不參與計算，并且要保證后兩種情況合法，所以還要判斷i, j的大小，滿足第三種情況至少要有 3 只黑鼠，滿足第四種情況要有 1 只白鼠和 2 只黑鼠，
具體的代碼實作如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void debug_out(){
cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef local
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif
double dp[1005][1005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int w, b;
cin >> w >> b; //dp[w][b]
for(int i = 1; i <= w; i++) dp[i][0] = 1;
for(int j = 1; j <= b; j++) dp[0][j] = 0;
for(int i = 1; i <= w; i++){
for(int j = 1; j <= b; j++){
dp[i][j] += (double)i / (i + j); //公主一次就拿到了白鼠
if(j >= 3) dp[i][j] += dp[i][j - 3] * (double)j / (i + j) * (double)(j - 1) / (i + j - 1) * (double)(j - 2) / (i + j - 2); //公主和龍拿的都是黑鼠，跑出來的是黑鼠
if(i >= 1 && j >= 2) dp[i][j] += dp[i - 1][j - 2] * (double)j / (i + j) * (double)(j - 1) / (i + j - 1) * (double)i / (i + j - 2); //公主拿的是黑鼠，龍拿的是黑鼠，跑出來的是白鼠
}
}
printf("%.9lf", dp[w][b]);
return 0;
}
POJ 3071 Football
??先說說這道題的題意：有2n次方個隊，已知任意兩個隊之間每個隊獲勝的概率，比賽的規則是相鄰的兩個隊伍之間比賽，贏的繼續下一輪，輸的直接淘汰（相鄰的兩個隊伍是指，1和2，3和4，5和6…如果1和2中假設1贏了，1再跟3和4中的贏家比賽，這樣最后贏的那個隊一共打了n場比賽，題目的輸入是一個2 n的矩陣，第i行第j列的小數表示第i隊戰勝第j隊的概率，所以p[i][j] + p[j][i] == 1，要我們通過概率求得哪一支隊伍最終取得冠軍的概率最大，
??我們用dp[i][j]表示j參加的第i場比賽贏的概率，那么有遞推方程dp[i] [j] = dp[i - 1][j] * dp[ i - 1][k] * p[j][k]，j能參加的第i場比賽，那么j參加的第i - 1場肯定贏，所以此時有dp[i - 1][j]，第i場比賽j的對手是k，k能參加第i場比賽，那么k參加的第i - 1場比賽也肯定贏，所以此時有dp[i - 1][k]，因為我們是假設第i場比賽i戰勝j，所以有p[j][k]，
??這道題的關鍵是判斷第i輪，哪兩支隊可能進行比賽，因為每場比賽只允許相鄰兩支上一輪獲勝的隊伍比賽，這需要用到位運算，我們把1 ~ 2n支隊伍的編號變成0 ~ 2n - 1，再把每支隊伍的編號看成是二進制（第5支隊伍的編號為：101），假設n = 3， 所以第一輪比賽的隊伍：000 vs 001，010 vs 011，100 vs 101，110 vs 111，我們發現兩兩比賽的隊伍的編號只有最后一位是不同的；假設第一輪獲勝的隊伍是第1支（編號為0，二進制：000），第4支（編號為3，二進制：011），第6支（編號為5，101），第7支（編號為6，110），所以此時第二輪比賽：000 vs 011，101 vs 110，這時我們又發現這一輪兩兩比賽的隊伍的編號只要倒數第二位是不同的，以此類推…最終我發現了規律：第i輪比賽能進行比賽的隊伍j和k需滿足：(((j - 1) >> (i - 1)) ^ 1) == ((k - 1) >> (i - 1))，j - 1和k - 1的含義相當于我們上面第i支隊伍的編號為i - 1，當進行到第i輪的時候，我們判斷的是編號的倒數第i位（編號右移i - 1，看最后一位（與1異或之后）是否與其他隊伍的編號相同），這一系列的操作就是為了判斷兩支隊伍的編號的二進制是不是除了倒數第i位（倒數第i位之后的數不管）之外，前面的都一樣，若滿足條件，這兩支隊伍在第i輪就有可能進行比賽，
??最后遍歷dp[n][i]，找到最大的概率，記錄并輸出dp[n][i]中的i即可，
具體的代碼實作如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
double dp[130][130], p[130][130], maxx;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
while(cin >> n){
if(n == -1) break;
memset(dp, 0, sizeof dp);
int len = 1 << n, s;
for(int i = 1; i <= len; i++){
for(int j = 1; j <= len; j++){
cin >> p[i][j];
}
}
for(int i = 1; i <= len; i++) dp[0][i] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= len; j++){
for(int k = 1; k <= len; k++){
if((((j - 1) >> (i - 1)) ^ 1) == ((k - 1) >> (i - 1))) dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * p[j][k];
}
}
}
maxx = 0;
for(int i = 1; i <= len; i++){
if(dp[n][i] > maxx){
maxx = dp[n][i];
s = i;
}
}
cout << s << endl;
}
return 0;
}
CodeForces 768 D - Jon and Orbs
??題目大意：有k種物品，每天只能取一種物品，取后放回，有q組詢問，每次給出一個數pi，求取物品的期望天數n滿足全取完k種物品的概率不小于pi / 2000，
??我們用dp[i][j]表示第i天已經出現了j種物品的概率，狀態轉移方程：dp[i][j] = dp[i - 1][j] * j / k + dp[i - 1][j - 1] * (k - j + 1) / k;所以我們要開始從第一天開始遍歷，終止條件是p <= 1000（題目給出了p1的范圍），這道題相當于在動態轉移的程序中打表了當1 <= p <= 1000時的所有情況，在特定的前i天對已經取得了j（1 ~ k）種物品進行遞推求出概率，到最后求出來dp[i][k]之后進行while(p <= 1000 && dp[i][k] * 2000 > p) s[p++] = i; 把符合概率條件的p記錄為i，
具體的代碼實作如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void debug_out(){
cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef local
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif
double dp[10005][1005];
LL s[1005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, k, q, p = 1;
cin >> k >> q;
dp[0][0] = 1;
for(int i = 1; p <= 1000; i++){
for(int j = 1; j <= k; j++){
dp[i][j] = (dp[i - 1][j] * j + dp[i - 1][j - 1] * (k - j + 1)) / k;
}
while(p <= 1000 && dp[i][k] * 2000 > p){
s[p++] = i;
}
}
while(q--){
cin >> n;
cout << s[n] << endl;
}
return 0;
}
POJ2096 Collecting Bugs
??看英文看了半天的廢話，這道題的大意就是：一個軟體有s個子系統，會產生n種bug，某人一天發現一個bug，這個bug屬于某種bug分類，也屬于某個子系統，每個bug屬于某個子系統的概率是1 / s，屬于某種bug分類的概率是1 / n，求發現n種bug，且s個子系統都找到bug的期望天數，
??這道題就屬于期望dp中，終止狀態確定時用逆推刷表，我們用dp[i][j]表示以及找到了i中bug分類，這些bug屬于j個子系統時，達到目標狀態的期望天數，我們這道題的目標是找到n中bug分類，s個子系統的bug，那么就有dp[i][j] = 0，因為此時已經達到了目標狀態，不需要更多的天數去發現bug了，達到目標狀態的期望天數自然就為0，于是就已目標狀態為起點開始遞推，答案是dp[i][j]，
dp[i][j]的狀態轉移情況：
??1、dp[i][j]，發現一個bug屬于已經發現的i種bug分類，j個子系統，這情況發生的概率是：p1 = i / n * j / s
??2、dp[i][j + 1]，發現一個bug屬于已經發現的i種bug分類，但不屬于已經發現的j個子系統，這種情況發生的概率是：p2 = i / n * (s - j) / s
??3、dp[i + 1][j]，發現一個bug不屬于已經發現的i中bug分類，屬于已經發現的j個子系統，這種情況發生的概率是：p3 = (n - i) / i * j / s
??4、dp[i + 1][j + 1]，發現的一個bug既不屬于已經發現的i個子系統，也不屬于已經發現的j個子系統，這種情況發生的概率是：p4 = (n - i) / i * (s - j) / j
??因為我們是從終止狀態逆推到初始狀態的，每一個狀態到終止狀態期望的天數，都是由它轉移到若干狀態的概率 與 其對應狀態到終止狀態期望天數的乘積 相累加得到的（因為是再找一個bug才能轉移，所以還要加1），所以我們可以得到狀態轉移方程：dp[i][j] = p1 * dp[i][j] + p2 * dp[i][j + 1] + p3 * dp[i + 1][j] + p4 * dp[i + 1][j + 1] + 1，把等式兩邊的dp[i][j]合并可得最終的狀態轉移方程：dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j + dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) / (n * s - i * j);
??最終得到的dp[0][0]即為發現n種bug，且s個子系統都找到bug的期望天數，
具體的代碼實作如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
double dp[1005][1005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, s;
cin >> n >> s;
for(int i = n; i >= 0; i--){
for(int j = s; j >= 0; j--){
if(n == i && s == j) continue; //因為是終止狀態，初始化就為0，不用處理
dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j + dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) / (n * s - i * j);
}
}
printf("%.4lf", dp[0][0]);
return 0;
}
P1850 [NOIP2016 提高組] 換教室
??題目比較長，我先說說大概的意思：牛牛要上n個時間段的課，第i個時間段在ci號教室，可以申請換到di號教室，申請成功的概率為pi，至多可以申請m節課進行交換，第i個時間段的課上完后要走到第i + 1個時間段的教室，給出一張圖v個教室e條路，移動會消耗體力，申請哪幾門課程可以使他因在教室間移動耗費的體力值的總和的期望值最小，也就是求出最小的期望路程和，
??對于這個無向連通圖，先用Floyd求出最短路，為后續狀態轉移帶來便利（我們用f[a][b]表示第a間教室到第b間教室之間的距離），假設現在在第i - 1個時間段，考慮去第i個時間段上課，如果申請從ci號教室交換到第di號教室上課，則有pi的概率申請成功，1 - pi的概率申請不成功，而且每人只有m個申請的機會（無論申請成功與否，都看作用了申請的機會），求出到第n個時間段走過的最小期望路程和，我們定義dp[i][j][0]表示前i個時間段已經申請了j次，且第i個時間段不申請換教室；dp[i][j][1]表示前i個時間段已經申請了j次，且第i個時間段申請換教室，最終最小的期望路程和就是min{dp[n][j][0], dp[n][j][1]}，j的取值范圍是0 ~ m，注意初始化邊界dp[1][0][0] = dp[1][1][1] = 0，
??現在考慮dp[i][j][0/1]的狀態轉移：
??一：dp[i][j][0]，第i個時間段不換教室，此時的狀態可能是第i - 1個時間段沒申請換教室轉移來的，也有可能是第i - 1個時間段申請換教室（有pi - 1概率申請成功）轉移來的，前者為：dp[i - 1][j][0] + f[c[i - 1]][c[i]]，對于后者的情況：如果申請成功，f[d[i - 1]][c[i]] * p[i - 1]；如果申請失敗，f[c[i - 1]][c[i]] * (1 - p[i - 1])，綜合起來，后者為：dp[i - 1][j ][1] + f[d[i - 1]][c[i]] * p[i - 1] + f[c[i - 1]][c[i]] * (1 - p[i - 1])，取前者和后者路程期望的最小值，所以情況一的轉移方程：dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]], (dp[i - 1][j][1] + f[d[i - 1]][c[i]] * p[i - 1] + f[c[i - 1]][c[i]] * (1 - p[i - 1])));
??二：dp[i][j][1]，第i個時間段申請換教室，此時的狀態可能是第i - 1個時間段沒申請換教室轉移來的，也有可能是第i - 1個時間段申請換教室（有pi - 1概率申請成功）轉移來的，前者：如果第i個時間段申請成功，f[c[i - 1]][d[i]] * p[i]，如果第i個時間段申請不成功，f[c[i - 1][c[i]]] * (1 - p[i])，綜合起來，前者：dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] + f[c[i - 1]][c[i]] * (1 - p[i])，后者要分成四種情況（第i - 1和i個時間段都申請換教室了，都有申請成功和失敗兩種情況），如果都申請成功，f[d[i - 1]][d[i]] * p[i - 1] * p[i]；如果都申請失敗，f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1])；如果第i - 1個時間段申請成功，第i個時間段申請失敗，f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i])；如果第i - 1個時間段申請失敗，第i個時間段申請成功，f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i]，綜合四種情況起來，后者為：dp[i - 1][j - 1][1] + f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]) + f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + f[d[i - 1]][d[i]] * p[i - 1] * p[i]，取前者和后者路程期望的最小值，所以情況二的轉移方程：dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] + f[c[i - 1]][c[i]] * (1 - p[i]), dp[i - 1][j - 1][1] + f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]) + f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + f[d[i - 1]][d[i]] * p[i - 1] * p[i]);
??最后，取dp[n][j][0/1]的最小值（j的范圍：1 ~ m）即為最終的答案，
具體的代碼實作如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void debug_out(){
cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef local
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif
double dp[2005][2005][2], p[2005], s = 1e9;
int c[2005], d[2005], f[2005][2005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, v, e, a, b, w;
cin >> n >> m >> v >> e;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i <= n; i++) cin >> d[i];
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= v; i++){
for(int j = 1; j < i; j++){
f[i][j] = f[j][i] = 1e9;
}
}
for(int i = 1; i <= e; i++){
cin >> a >> b >> w;
f[a][b] = f[b][a] = min(w, f[a][b]);
}
for(int k = 1; k <= v; k++){
for(int i = 1; i <= v; i++){
for(int j = 1; j < i; j++){
if(f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[j][i] = f[i][k] + f[k][j];
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
dp[i][j][0] = dp[i][j][1] = 1e9;
}
}
dp[1][0][0] = dp[1][1][1] = 0;
for(int i = 2; i <= n; i++){
for(int j = 0; j <= min(i, m); j++){
dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]], (dp[i - 1][j][1] + f[d[i - 1]][c[i]] * p[i - 1] + f[c[i - 1]][c[i]] * (1 - p[i - 1])));
if(j != 0) dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] + f[c[i - 1]][c[i]] * (1 - p[i]), dp[i - 1][j - 1][1] + f[c[i - 1]][c[i]] * (1 - p[i]) * (1 - p[i - 1]) + f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + f[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + f[d[i - 1]][d[i]] * p[i - 1] * p[i]);
}
}
for(int j = 0; j <= m; j++) s = min(s, min(dp[n][j][0], dp[n][j][1]));
printf("%.2lf", s);
return 0;
}
HDU3853 LOOPS
??這道題的意思是：有一個R * C的迷宮布局，有個人想從起點(1, 1)出發，走到終點(R, C)，他要走的話只能向下或者向下走，但每個格子都有讓人停留在原地，往右走一個，往下走一格的概率，已知每走一格消耗2點能量，求出最后所需要的能量期望，
??輸入的時候，首先輸入的是R和C，然后依次給出如果經過每個格子的時候，停在原地、向右走、向下走的概率，我們可以用一個三維陣列a[i][j][0/1/2]把概率存起來，第三維012分別表示停在原地、向右走、向下走，這道題是期望dp，用逆推的思想求的期望，用dp[i][j]表示當人走到第i行第j列個格子的時候，要到終點（r, c）所需的期望能量，所以dp[r][c] = 0，我們目標是求dp[1][1]，狀態轉移：dp[i][j] = dp[i][j] * a[i][j][0] +dp[i][j + 1] *a[i][j][1] + dp[i + 1][j] * a[i][j][2] + 2，化簡后可得：dp[i][j] = (dp[i][j + 1] * a[i][j][1] + dp[i + 1][j] * a[i][j][2] + 2) / (1 - a[i][j][0]);最后得到的dp[1][1]即為(1, 1)到終點(r, c)的能量期望，
具體的代碼實作如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void debug_out(){
cerr << endl;
}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef local
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...) 55
#endif
double dp[1005][1005], a[1005][1005][3];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int r, c;
while(~scanf("%d%d", &r, &c)){
memset(dp, 0, sizeof dp);
for(int i = 1; i <= r; i++){
for(int j = 1; j <= c; j++){
for(int k = 0; k <= 2; k++){
scanf("%lf", &a[i][j][k]);
}
}
}
for(int i = r; i >= 1; i--){
for(int j = c; j >= 1; j--){
if(i == r && j == c) continue; //終點初始化為0，不用轉移
if(fabs(1 - a[i][j][0]) < 1e-9) continue; //a[i][j][0] == 1說明停在了這個格子了
dp[i][j] = (dp[i][j + 1] * a[i][j][1] + dp[i + 1][j] * a[i][j][2] + 2) / (1 - a[i][j][0]);
debug(dp[i][j]);
}
}
printf("%.3lf\n", dp[1][1]);
}
return 0;
}
總結：
??DP求期望的題目在對具體是求一個值或是最優化問題上會對方程得到轉移方式有一些影響，但無論是DP求概率還是DP求期望，總是離不開概率知識和列出、化簡計算公式的步驟，在寫狀態轉移方程時需要思考的細節也類似，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/264537.html
標籤：其他