动态规划
一开始定义为dp[l1][l2][l3][dd]，表示用l1个{}，l2个[]，l3个()，深度为dd的方案数，后来不行。参考别人后，dp[l1][l2][l3][dd]表示深度小于等于dd的方案数，那么答案是
dp[l1][l2][l3][dd]-dp[l1][l2][l3][dd-1]
可以用分块和整块的思想来看这个问题
好像[[()][]] 这类的我们可以说它是整块，[][]()，这类的我们可以说它是分块，我们在构建的dp数组的时候就是把其当做是分块来处理，然后使用乘法原理
例如dp[l1][l2][l3][dd]，我们可以先构建一个小分块，用小分块的方案数*其实括号能组成的方案数，而这个小分块，其实本身是一个整块
我们来看这个小分块，最外层可以是()，[]，{}
如果是()，那么里面必定全部是()，由题意的优先级可知,所以假设用i个()组成小分块，则dp[l1][l2][l3][dd]=dp[0][0][i-1][dd-1]*dp[l1][l2][l3-i][dd]
也就是用i个()组成小分块，已经用掉一个做外层，所以只剩下i-1个，并且深度也应该下降为dd-1，而剩下l1个{}，l2个[]，l3-i个()，他们再组合，两者相乘
同样的，如果小分块使用[]作为外层，那么里面可以使用[]和()，整个小分块假设使用了j个[],i个()，则dp[l1][l2][l3][dd]=dp[0][j-1][i][dd-1]*dp[l1][l2-j][l3-i][dd]
意思就是，用j个[],i个()去构建小分块，已经用掉一个[]作为外层，因此深度也应该下降为dd-1，剩下l1个{}，l2-j个[]，l3-i个()，他们再组合，两者相乘
同样的，如果小分块使用{}作为外层，那么里面可以使用{},[],()，假设分别用了k，j，i个，那么dp[l1][l2][l3][dd]=dp[k-1][j][i][dd-1]*dp[l1-k][l2-j][l3-i][dd]
小分块用掉一个{}作为外层，深度也应该下降为dd-1，再用剩下的括号去组合，两者相乘
整个算法中需要按照优先级去枚举小分块最外层的类型，应该()在最外层，接着是[]，{}，这个也是 值得思考的地方
接着就是记忆化实现，感觉这东西递推不好写
搜索的话就要知道边界
1.l1=0 && l2=0 && l3=0 ， dp值为1
1.dd=0时，dp值为0
#include#include #define MOD 11380//#define LOCALint dp[15][15][15][35];bool vis[15][15][15][35];int dfs(int l1,int l2,int l3,int dd){ if(!l1 && !l2 && !l3) { vis[l1][l2][l3][dd] = true; return dp[l1][l2][l3][dd] = 1; } if(!dd) { vis[l1][l2][l3][dd] = true; return dp[l1][l2][l3][dd] = 0; } if(vis[l1][l2][l3][dd]) return dp[l1][l2][l3][dd]; int ans = 0; for(int i=0;i<=l3;i++) { if(i) { ans = (ans+dfs(0,0,i-1,dd-1) * dfs(l1,l2,l3-i,dd)) % MOD; ans %= MOD; } for(int j=0;j<=l2;j++) { if(j) { ans = (ans+dfs(0,j-1,i,dd-1) * dfs(l1,l2-j,l3-i,dd)) % MOD; ans %= MOD; } for(int k=1;k<=l1;k++) { ans = (ans+dfs(k-1,j,i,dd-1) * dfs(l1-k,l2-j,l3-i,dd)) % MOD; ans %= MOD; } } } vis[l1][l2][l3][dd] = true; return dp[l1][l2][l3][dd] = ans;}int main(){ #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int l1,l2,l3,dd; memset(vis,0,sizeof(vis)); scanf("%d%d%d%d",&l1,&l2,&l3,&dd); dp[l1][l2][l3][dd]=dfs(l1,l2,l3,dd); if(dd) dp[l1][l2][l3][dd-1]=dfs(l1,l2,l3,dd-1); //dp[l1][l2][l3][dd-1]=dfs(l1,l2,l3,dd-1); if(!dd) { printf("%d\n",dp[l1][l2][l3][dd]); return 0; } int a1=dp[l1][l2][l3][dd] , a2=dp[l1][l2][l3][dd-1]; //printf("%d %d\n",a1,a2); printf("%d\n",((a1-a2)%MOD+MOD)%MOD); return 0;}