POJ 1187 隕石的秘密 （線性DP）

題意：

公元11380年，一顆巨大的隕石墜落在南極。于是，災難降臨了，地球上出現了一系列反常的現象。當人們焦急萬分的時候，一支中國科學家組成的南極考察隊趕到了出事地點。經過一番偵察，科學家們發現隕石上刻有若干行密文，每一行都包含5個整數：?
1 1 1 1 6?
0 0 6 3 57?
8 0 11 3 2845?
著名的科學家SS發現，這些密文實際上是一種復雜運算的結果。為了便于大家理解這種運算，他定義了一種SS表達式：?
1． SS表達式是僅由'{'，'}'，'['，']'，'（'，'）'組成的字符串。?
2． 一個空串是SS表達式。?
3． 如果A是SS表達式，且A中不含字符'{'，'}'，'['，']'，則(A)是SS表達式。?
4． 如果A是SS表達式，且A中不含字符'{'，'}'，則[A]是SS表達式。?
5． 如果A是SS表達式，則{A}是SS表達式。?
6． 如果A和B都是SS表達式，則AB也是SS表達式。?


例如?
()(())[]?
{()[()]}?
{{[[(())]]}}?
都是SS表達式。?
而?
()([])()?
[()?
不是SS表達式。?

一個SS表達式E的深度D(E)定義如下：?
?
例如(){()}[]的深度為2。?

密文中的復雜運算是這樣進行的：?
設密文中每行前4個數依次為L1，L2，L3，D，求出所有深度為D，含有L1對{}，L2對[]，L3對()的SS串的個數，并用這個數對當前的年份11380求余數，這個余數就是密文中每行的第5個數，我們稱之為?神秘數?。?
密文中某些行的第五個數已經模糊不清，而這些數字正是揭開隕石秘密的鑰匙。現在科學家們聘請你來計算這個神秘數。?

思路：

初始想法：我們令dp[l1][l2][l3][d]為用了l1個小括號，l2個中括號，l3個大括號，深度恰好為d時的方案數，現在我們來找狀態之間的聯系。然而我們可以發現一個殘酷的事實，光用4個變量無法很好的表示一個狀態。比如，我們添加一個小括號，當前狀態帶表的括號序列中，有一部分序列的深度增加了，有一部分沒有增加，所以為了正確的轉移狀態，正常想法就是用狀壓之類的記錄具體方案，然而這個題就。。。

我們可以發現，新添加一個括號，括號序列的深度最多增加1，要么就不變，所以，如果dp[l1][l2][l3][d]表示的是用了l1個小括號，l2個中括號，l3個大括號，深度小于等于d的方案數就很好辦了，添加一個括號后從深度小于等于d的狀態轉移到深度小于等于d + 1的狀態。

則等于d的方案數 = 小于等于d的方案數 - 小于等于d - 1的方案數。

還有一個問題，我們怎么不重不漏的寫出狀態轉移的過程？我們可以發現，所有深度小于等于d的括號序列是由若干個深度小于等于d的嵌套的括號構成的，所以，我們可以這樣轉移狀態：我們把當前狀態分成2個部分，一個部分用來形成嵌套的括號，另一部分對應的是那個狀態的方案數。我們枚舉向最里面添加什么括號。因為大括號外面不能有其它的括號，所以當在最里面套大括號時，只能有大括號。例如，當前嵌套形的括號是{[()]},我們不能向里面添加{},但是添加小括號可以，變成{[(())]}。同理，枚舉狀態時，當添加的是中括號時，外面只能是中括號和大括號。

思路和代碼實現參考了這篇博客：https://blog.csdn.net/Flying_Stones_Sure/article/details/7954114

代碼：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int mod = 11380;
int dp[11][11][11][31];
bool v[11][11][11][31];
int dfs(int l1, int l2, int l3, int deep) {if (l1 == 0 && l2 == 0 && l3 == 0) {v[l1][l2][l3][deep] = 1;return dp[l1][l2][l3][deep] = 1;}if (deep == 0) {v[l1][l2][l3][deep] = 1;return dp[l1][l2][l3][deep]  = 0;}if (v[l1][l2][l3][deep])return dp[l1][l2][l3][deep];int ans = 0;for (int i = 0; i <= l3; i++) {if (i) {ans = (ans + dfs(0 , 0, i - 1, deep - 1) * dfs(l1, l2, l3 - i, deep)) % mod;}for (int j = 0 ;j <= l2; j++) {if (j) {ans = (ans + dfs(0, j - 1, i, deep - 1) * dfs(l1, l2 - j, l3 - i, deep)) % mod;}for (int k = 1; k <= l1; k++) {ans = (ans + dfs(k - 1, j, i, deep - 1) * dfs(l1 - k, l2 - j, l3 - i, deep)) % mod;}}}v[l1][l2][l3][deep] = 1;return dp[l1][l2][l3][deep] = ans;
}
int main() {int n, m, d, t;while(~scanf("%d%d%d%d", &n, &m, &t, &d)) {dfs(n, m, t, d);if(d) dfs(n, m ,t, d - 1);if(d) {printf("%d\n", (dp[n][m][t][d] - dp[n][m][t][d - 1] + mod ) % mod);} else {printf("%d\n", dp[n][m][t][d]);}}
}