Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531189783000,"title":" F - Coloring Brackets","dislikeCnt":1,"content":"四维DP。。。\n对于只有一组匹配的“()“,有dp【0】【1】【1】【0】,dp【0】【1】【2】【0】,dp【0】【1】【0】【1】,dp【0】【1】【0】【2】四种情况。\n对于多组但成包含结构的“()”其状态转移方程为\ndp【i】【j】【l】【r】\u003ddp【i】【j】【l】【r】+dp【i+1】【j-1】【k】【q】;(q!\u003dl或r)\n对于多组且不含包含结构的“()”(无交集的子集)其状态转移方程为\ndp【i】【j】【l】【r】\u003d(dp【i】【j】【l】【r】+dp【i】【p】【l】【k】*dp【p+1】【j】【q】【r】;(i\u003cp\u003cj,k!\u003dp(除k\u003d\u003dp\u003d\u003d0))\n\n```\n#include\u003ccstdio\u003e\n#include\u003cstring\u003e\n#include\u003ccstring\u003e\n#include\u003calgorithm\u003e\n#include\u003ciostream\u003e\n#define mod 1000000007\nusing namespace std;\ntypedef long long ll;\nstring s; //dp【i】【j】【l】【r】用于记录第i个为(的颜色为l\nll dp[710][710][3][3],e[710],o[710];//第j个为(的颜色为r时的方案数 \nvoid in(int len){ //对“(”和“)”进行匹配 \n int p\u003d0;\n for(int i\u003d0;i\u003clen;i++){ \n if(s[i]\u003d\u003d\u0027(\u0027)\n o[p++]\u003di; //第p个“(”的下标为i \n else{ //(因为i之前e数组的值都为0,因此可以将e数组与o数组合并)\n e[i]\u003do[p-1]; //第i个“)”对应的下标为第p-1个“)”的下标 ,即将o数组上的内容转移到e数组 \n e[o[p-1]]\u003di; //第 o[p-1]个“)”对应的下标为i \n p--;\n }\n } \n}\nvoid dfs(int i,int j){\n if(i+1\u003d\u003dj){ //若只有一组() \n dp[i][j][0][1]\u003d1;\n dp[i][j][1][0]\u003d1;\n dp[i][j][0][2]\u003d1;\n dp[i][j][2][0]\u003d1;\n return ;\n }\n if(e[i]\u003d\u003dj){ //最后一个) 的下标与区间右端点对应 \n dfs(i+1,j-1);//缩小范围,递归 \n for(int l\u003d0;l\u003c3;l++){//枚举不同颜色的方案数 \n for(int r\u003d0;r\u003c3;r++) {\n if(r!\u003d1)dp[i][j][0][1]\u003d(dp[i][j][0][1]+dp[i+1][j-1][l][r])%mod;//由于j的值 \n if(r!\u003d1)dp[i][j][1][0]\u003d(dp[i][j][1][0]+dp[i+1][j-1][l][r])%mod;//可能会使方案数异常巨大\n if(r!\u003d2)dp[i][j][0][2]\u003d(dp[i][j][0][2]+dp[i+1][j-1][l][r])%mod;//因此每步都模一遍\n if(r!\u003d2)dp[i][j][2][0]\u003d(dp[i][j][2][0]+dp[i+1][j-1][l][r])%mod;\n }\n }\n return ;\n }\n else{\n int p\u003de[i];//对两个区间的方案数进行计算 \n dfs(i,p);\n dfs(p+1,j);\n for(int l\u003d0;l\u003c3;l++)\n for(int r\u003d0;r\u003c3;r++)\n for(int k\u003d0;k\u003c3;k++)\n for(int q\u003d0;q\u003c3;q++)\n if(!((k\u003d\u003d1\u0026\u0026q\u003d\u003d1)||(k\u003d\u003d2\u0026\u0026q\u003d\u003d2)))\n dp[i][j][l][r]\u003d(dp[i][j][l][r]+(dp[i][p][l][k]*dp[p+1][j][q][r])%mod)%mod;\n }\n}\nint main(){\n cin\u003e\u003es;\n in(s.length());\n dfs(0,s.length()-1);\n ll ans\u003d0;\n for(int l\u003d0;l\u003c3;l++)\n for(int r\u003d0;r\u003c3;r++)\n ans\u003d(ans+dp[0][s.length()-1][l][r])%mod;\n cout\u003c\u003cans\u003c\u003cendl;\n return 0;\n}\n```","threadId":31215,"likeCnt":0,"createTime":1531189783000,"isWorkbook":false,"viewCnt":2042,"openness":2,"fav":false,"id":497,"trustable":false}