ToB企服应用市场:ToB评测及商务社交产业平台

标题: POJ3254 Corn Fields（状压DP） [打印本页]

---

作者: 干翻全岛蛙蛙    时间: 2022-8-10 12:01
标题: POJ3254 Corn Fields（状压DP）
dp[j]表示第i行第j个状态时，前i行得到的方案数，该状态可由前一行的状态转移过来。
本题重点在于合法性检测：每一行都用一个二进制数表示，1.二进制数不能有相邻的1；2.要和原地图匹配；3.上下两行不能有冲突。
预处理地图时将0换成1，方便进行2号检测，用位运算&可以实现。
[code] 1 #include 2 #include 3 using namespace std; 4 #define mod 100000000 5 int m,n,top=0; 6 int state[600];//储存合法状态  7 int dp[20][600];//dp[j]表示第i行，第j种编号时，前i行的可行方案数  8 int cur[20]; 9 10 bool check(int x){//有相邻的1则不合法 11     if(x&x

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4