郑州网站制作价格,外包什么意思,域名注册商修改dns,最新企业名录搜索软件目录 建议有状压基础再食用#xff1a;本题的状态转移方程是 dp代码片:参考代码 建议有状压基础再食用#xff1a;
n行m列 等价 n列m行 #xff0c;因为n比较小#xff0c;int是32位足够了#xff0c;我们用比特位统计每一行的状态。
本题的状态转移方程是
dp[h][i][j]… 目录 建议有状压基础再食用本题的状态转移方程是 dp代码片:参考代码 建议有状压基础再食用
n行m列 等价 n列m行 因为n比较小int是32位足够了我们用比特位统计每一行的状态。
本题的状态转移方程是
dp[h][i][j][num] (dp[h][i][j][num] dp[h - 1][j][ii][num - nums[i]])%mod; h是行数i和j表示本行状态和上一行状态num表示个数。 nums[i]是情况为 i 时的bit位为1的数目提前可以统计一下。 dp的值就是求的情况数。
很难理解其实我们先不看i 和 j只看行数和num这才是dp的样子。 然后加上i和j状态压缩就是状压dp了。
(动态规划是有条理的遍历是全面覆盖的num所有可以的情况都会遍历。本行i是0也会所以只有前几行放棋子的后面全是0也会遍历到的。)
dp代码片:
前一行和本行情况的比特位存在隔2的 和 前两行和本行情况的比特位存在隔1的情况直接略去也就是马会互吃的情况。
//初始化
dp[0][0][0][0] 1;//0行什么也不放。第一行肯定会摸一下方案数是1
//for (int h 1; h m; h)
{for (int i 0; i (1ll n); i)//本行{for (int j 0; j (1ll n); j)//前一行{for (int ii 0; ii (1ll n); ii)//前两行{for (int num nums[i]; num k; num){if ((i 2 j) || (i 2 j))continue;if ((i 1 ii) || (i 1 ii))continue;dp[h][i][j][num] (dp[h][i][j][num] dp[h - 1][j][ii][num - nums[i]])%mod;}}}}
}参考代码
int n,m,k;int countb(int aim)
{int ret 0;for (int i 0; i n; i){if (aim (1ll i)){ret;}}return ret;
}void solve()
{cin n m k;//n行m列 等价 n列m行//n列可统计状压vectorintnums(1 n);for (int i 0; i (1ll n); i){nums[i] countb(i);}vectorvectorvectorvectorintdp(m1, vectorvectorvectorint( 1lln, vectorvectorint(1ll n,vectorint(k1) ) ) );//第几行 本行状态 前一行状态 个数 方案数//dp[0][0][0][0] 1;//0行什么也不放。第一行肯定会摸一下方案数是1//for (int h 1; h m; h){for (int i 0; i (1ll n); i)//本行{for (int j 0; j (1ll n); j)//前一行{for (int ii 0; ii (1ll n); ii)//前两行{for (int num nums[i]; num k; num){if ((i 2 j) || (i 2 j))continue;if ((i 1 ii) || (i 1 ii))continue;dp[h][i][j][num] (dp[h][i][j][num] dp[h - 1][j][ii][num - nums[i]])%mod;}}}}}//后面都是0也包括了只在前几行放的。。//动归int ans 0;for (int i 0; i (1ll n); i)//本行{for (int j 0; j (1ll n); j)//前一行{ans (ans dp[m][i][j][k]) % mod;}}cout ans;return;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t 1;//cin t;for (int i 1; i t; i){solve();}return 0;
}
