海口网站建设服务,做视频点播网站的要求,网站前置审批查询,网页应用生成器【题目解析】蓝桥杯23国赛C中高级组 - 斗鱼养殖场
题目链接跳转#xff1a;点击跳转
前置知识#xff1a;
了解过基本的动态规划。熟练掌握二进制的位运算。
题解思路
这是一道典型的状压动态规划问题。设 d p i , j dp_{i, j} dpi,j 表示遍历到第 i i i 行的时候中高级组 - 斗鱼养殖场
题目链接跳转点击跳转
前置知识
了解过基本的动态规划。熟练掌握二进制的位运算。
题解思路
这是一道典型的状压动态规划问题。设 d p i , j dp_{i, j} dpi,j 表示遍历到第 i i i 行的时候当前行以 j ( b a s e 2 ) j_{(base2)} j(base2) 的形式排列乌龟可以构成的方案数。
对于每一行的方案我们可以用一个二进制来表示。例如二进制数字 10100 10100 10100表示有一个横向长度为 5 5 5 的场地中第 1 , 3 1, 3 1,3 号位置分别放置了一只小乌龟。因此每一种摆放状态都可以用一个二进制数字来表示。我们也可以通过遍历的方式来遍历出二进制的每一种摆放状态。
首先我们预处理出横排所有放置乌龟的合法情况。根据题意两个乌龟不能相邻放置因此在二进制中不能有两个 1 1 1 相邻。如何预处理出这种情况呢我们可以使用位运算的方法
如果存在一个二进制数字有两个 1 1 1 相邻那么如果我们对这个数字 x x x 进行位运算操作 (x 1) x 的结果或 (x 1) x 的结果必定大于等于 1 1 1。我们通过把这种情况排除在外。同时我们还需要注意有些格子中不能放置乌龟。这一步也可以通过二进制的方法预处理掉如果网箱在第 i i i 一个格子中不能放置乌龟那么在枚举所有方案数的时候直接忽略掉第 i i i 位为 1 1 1 的情况即可。
接下来如何保证上下两行的乌龟不冲突假如上一行的摆放状态是 y y y当前行的摆放状态为 j j j如果 i j 的结果大于等于 1 1 1也可以证明有两个数字 1 1 1 在同一位置上。因此我们也需要把这种情况排除在外。
综上所述我们可以得出状态转移方程 d p i , j d p i , j d p i − 1 , k dp_{i, j} dp_{i, j} dp_{i-1, k} dpi,jdpi,jdpi−1,k。其中 j j j 和 k k k 表示所有横排合法的方案。答案就是 A N S ∑ j 0 2 M − 1 d p N , j \mathtt{ANS} \sum_{j0}^{2^M-1}{dp_{N, j}} ANS∑j02M−1dpN,j。
状态的初始化也很简单另 d p 0 , 0 1 dp_{0, 0} 1 dp0,01表示一只乌龟都不放有一种摆放方案。
时间复杂度
通过观察上述代码在枚举所有状态和转移状态的时候有三层循环分别是枚举当前行、枚举当前行的合法摆放情况以及枚举上一行的摆放情况。因此总时间复杂度约为 O ( n × 2 M × 2 M ) O ( n × 2 M 2 ) O ( n × 4 M ) O(n \times 2^M \times 2^M) O(n \times 2^{M^2}) O(n \times 4^M) O(n×2M×2M)O(n×2M2)O(n×4M)。但由于合法的摆放数量远远少于 2 M 2^M 2M因此实际情况下程序运行的速度会快许多。
代码实现
本题的代码实现如下。在输出的时候需要减一因为不放置也是一种合法情况根据题目要求需要把这一合法情况排除。
#include iostream
using namespace std;const int MOD 1e97;
int n, m, ans;
int arr[505][505];
// 所有横排合法的情况。
int terrain[505];
int ok[1050], cnt;
int dp[505][1050];int main(){cin n m;for (int i1; in; i){for (int j1; jm; j){cin arr[i][j];}}// 预处理非法地形。for (int i1; in; i){for (int j1; jm; j){terrain[i] (terrain[i] 1) !arr[i][j];}}// 预处理出所有横排的合法情况。for (int i0; i(1m); i){if (((i1)|(i1)) i) continue;ok[cnt] i;}dp[0][1] 1;// 枚举。for (int i1; in; i){for (int s11; s1cnt; s1){ // 枚举当前行。if (ok[s1] terrain[i]) continue;for (int s21; s2cnt; s2){ // 枚举上一行。if (ok[s2] terrain[i-1]) continue;if (ok[s1] ok[s2]) continue;dp[i][s1] (dp[i][s1] dp[i-1][s2]) % MOD;}}}// 统计答案。int ans 0;for (int i1; icnt; i)ans (ans dp[n][i]) % MOD;cout ans - 1 endl;return 0;
}本题的 Python 代码如下Python 可以通过本题的所有测试点
MOD int(1e9 7)
n, m, ans 0, 0, 0
arr [[0] * 505 for _ in range(505)]
terrain [0] * 505
ok [0] * 1050
dp [[0] * 1050 for _ in range(505)]
cnt 0def main():global n, m, cnt, ans# 输入 n 和 mn, m map(int, input().split())# 输入 arr 数组for i in range(1, n 1):arr[i][1:m 1] map(int, input().split())# 预处理非法地形for i in range(1, n 1):for j in range(1, m 1):terrain[i] (terrain[i] 1) (1 - arr[i][j])# 预处理出所有横排的合法情况for i in range(1 m):if ((i 1) | (i 1)) i:continuecnt 1ok[cnt] idp[0][1] 1# 枚举for i in range(1, n 1):for s1 in range(1, cnt 1): # 枚举当前行if ok[s1] terrain[i]:continuefor s2 in range(1, cnt 1): # 枚举上一行if ok[s2] terrain[i - 1]:continueif ok[s1] ok[s2]:continuedp[i][s1] (dp[i][s1] dp[i - 1][s2]) % MOD# 统计答案ans 0for i in range(1, cnt 1):ans (ans dp[n][i]) % MODprint(ans - 1)if __name__ __main__:main()
再提供一个暴力解法用于对拍
#include iostream
using namespace std;const int MOD 1e97;
int n, m, ans;
int arr[505][505];
int dx[] {0, 1, -1, 0};
int dy[] {1, 0, 0, -1};// 深度优先搜索 Brute Force
void dfs(int x, int y){if (x n) {ans 1;ans % MOD;return ;}if (y m){dfs(x1, 1);return ;}if (arr[x][y] 0){dfs(x, y1);return ;}// 不放鱼dfs(x, y1);// 放鱼for (int i0; i4; i){int cx x dx[i];int cy y dy[i];if (cx 1 || cy 1 || cx n || cy m) continue;if (arr[cx][cy] 2) return ;}arr[x][y] 2;dfs(x, y1);arr[x][y] 1;return ;
}int main(){cin n m;for (int i1; in; i){for (int j1; jm; j){cin arr[i][j];}}// dfs 暴力dfs(1, 1);cout ans-1 endl;return 0;
}
