Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531123885000,"title":"hdu 5693 D Game","dislikeCnt":1,"content":"\n第一次写的时候智商爆炸,一遍AC\n于是后来就看不懂自己写了些什么了。。。。\n将符合条件数列先全部拆分成2~3个元素的集合,再逐一判断是否可以合并。\n最后用线性DP找出可消去的最多数字。\n\n```\n#include\u003ccstdio\u003e\n#include\u003ccstring\u003e\n#include\u003cmap\u003e\n#include\u003ciostream\u003e\nusing namespace std;\nint f[350],a[1500],dp[350][350];\nint main(){\n int t;\n scanf(\"%d\",\u0026t);\n while(t--){\n int n,m;\n scanf(\"%d%d\",\u0026n,\u0026m);\n memset(dp,0,sizeof(dp));\n memset(f,0,sizeof(f));\n for(int i\u003d1;i\u003c\u003dn;i++)scanf(\"%d\",\u0026a[i]);\n map\u003cint ,int \u003es;\n for(int i\u003d1;i\u003c\u003dm;i++){\n int x;scanf(\"%d\",\u0026x); //标记公差集合 \n s[x]\u003d1;\n }\n for(int len\u003d1;len\u003c\u003dn;len++){ //记录长度 \n for(int i\u003d1;i\u003c\u003dn;i++){ //记录左端点 \n int j\u003di+len; // 记录右端点 \n if(j\u003en)break; \n if(len\u003d\u003d1){\n if(s[a[j]-a[i]]\u003d\u003d1)\n dp[i][j]\u003d1;\n continue;\n }\n if(len\u003d\u003d2){\n if(a[j]-a[j-1]\u003d\u003da[j-1]-a[j-2]\u0026\u0026s[a[j]-a[j-1]]\u003d\u003d1)\n dp[i][j]\u003d1;\n continue;\n }\n if(j\u003c\u003dn){ //长度大于3后 \n if(s[a[j]-a[i]]\u0026\u0026dp[i+1][j-1]) //左端点与右端点之差符合公差 \n dp[i][j]\u003d1; //能否将中间全部消除 \n if(a[j]-a[i+1]\u003d\u003da[i+1]-a[i]\u0026\u0026s[a[j]-a[i+1]]\u0026\u0026dp[i+2][j-1]) //左端点与右端第二点与右端点之差符合公差 \n dp[i][j]\u003d1; //能否将中间全部消除\n if(a[j]-a[j-1]\u003d\u003da[j-1]-a[i]\u0026\u0026s[a[j]-a[j-1]]\u003d\u003d1\u0026\u0026dp[i+1][j-2]) //左端点与左端第二点与右端点之差符合公差 \n dp[i][j]\u003d1; //能否将中间全部消除\n for(int k\u003di;k\u003cj;k++) //可消除的区间能否合并 \n if(dp[i][k]\u003d\u003d1\u0026\u0026dp[k+1][j]\u003d\u003d1)\n dp[i][j]\u003d1;\n }\n else break;\n }\n }\n int ans\u003d0;\n for(int i\u003d1;i\u003c\u003dn;i++){\n f[i]\u003d0;\n for(int j\u003d1;j\u003c\u003di;j++){ //累计区间【j,i】内最多消去的数的个数 \n int flag\u003d0;\n if(dp[j][i]\u003d\u003d1)flag\u003di-j+1;\n f[i]\u003dmax(f[i],f[j-1]+flag);\n }\n ans\u003dmax(ans,f[i]);\n }\n printf(\"%d\\n\",ans);\n }\n}\n```","likeCnt":0,"createTime":1531117120000,"isWorkbook":false,"viewCnt":1815,"openness":2,"fav":false,"id":493,"trustable":false}