Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531402481000,"title":" E - 炮兵阵地","dislikeCnt":4,"content":"```\n#include\u003ciostream\u003e\n#include\u003ccstdlib\u003e\n#include\u003cstring\u003e\n#include\u003ccstdio\u003e\n#include\u003calgorithm\u003e\n#include\u003ccstring\u003e\nusing namespace std;\nint n,m,dp[110][75][75],h[110],sum[75],t[75],tot\u003d0,r\u003d0;//dp记录第i行状态为j到第i-1行状态为k的总数 \nint cal(int x){//计算其中1的个数\n int e\u003d0;\n while(x)e+\u003d(x\u00261),x\u003e\u003e\u003d1;\n return e;\n}\nint main(){\n scanf(\"%d%d\",\u0026n,\u0026m);\n for(int i\u003d1;i\u003c\u003dn;i++){\n for(int j\u003d0;j\u003cm;j++){\n char ch\u003dgetchar();\n while(ch!\u003d\u0027P\u0027\u0026\u0026ch!\u003d\u0027H\u0027)ch\u003dgetchar();\n if(ch\u003d\u003d\u0027H\u0027) h[i]|\u003d(1\u003c\u003cj);//预处理,h记录所有不能放的点 \n }\n }\n for(int i\u003d0;i\u003c(1\u003c\u003cm);i++) //预处理出第一行可能的状态 sum记录此时已被占的点的和\n if(!(i\u0026(i\u003c\u003c1))\u0026\u0026!(i\u0026(i\u003c\u003c2)))t[++tot]\u003di,sum[tot]\u003dcal(i);//t记录该行可以放的点的下标 \n for(int i\u003d1;i\u003c\u003dtot;i++) //预处理出第二行可能的状态 \n if(!(t[i]\u0026h[1]))dp[1][1][i]\u003dsum[i];//若该点可放,记录上一行状态为i时的该行状态 \n for(int i\u003d1;i\u003cn;i++) //枚举行 \n for(int j\u003d1;j\u003c\u003dtot;j++) //枚举该行状态 \n for(int k\u003d1;k\u003c\u003dtot;k++) // 枚举上一行状态 \n if(!(t[j]\u0026t[k])\u0026\u0026dp[i][j][k])\n for(int l\u003d1;l\u003c\u003dtot;l++) //枚举上两行状态\n if(!(t[l]\u0026t[j])\u0026\u0026!(t[l]\u0026t[k])\u0026\u0026!(t[l]\u0026h[i+1]))\n dp[i+1][k][l]\u003dmax(dp[i+1][k][l],dp[i][j][k]+sum[l]);\n for(int i\u003d1;i\u003c\u003dtot;i++) //取最大值 \n for(int j\u003d1;j\u003c\u003dtot;j++)\n r\u003dmax(r,dp[n][i][j]);\n printf(\"%d\",r);\n return 0;\n}\n\n```","threadId":31410,"likeCnt":1,"createTime":1531402481000,"isWorkbook":false,"viewCnt":2146,"openness":2,"fav":false,"id":513,"trustable":false}