wwwkal

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #最长回文子序列#

相当于求该字串与其翻转后的字串的最长公共子序列 #include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int max...

C++ 动态规划字符串

2022-04-21

1 519

题解 | #滑雪#

dfs+回溯对于点[i,j]，其最长路径由上下左右四个点决定。递归求解周围四点即可。由于路径严格递减，故不用担心无限循环的情况。 #include<iostream> using namespace std; const int MAXN = 105; int n, m; int m...

C++ 深度优先搜索回溯

2022-04-19

1 490

题解 | #最大子矩阵#

简单的思路求出所有以[i,j]为右下端点的所有矩阵大小，并比较其最值。时间复杂度N^4 dp 对于[i,j]，显然的其所有矩阵是[i+1,j]的子矩阵，多出的部分是第i行的前j个元素。那么我们就可以通过[i,j]求出[i+1,j] 关于求矩阵大小，可以先累加每行，再将行和累加；同样的，先算列和再累...

C++ 动态规划状态压缩

2022-04-15

0 459

题解 | #龙与地下城游戏问题#

与dp11相比，计算到达终点的最大值的同时，还需要记录路径上的最小值。 #include <iostream> using namespace std; int n, m; int dp[1005][1005]; //骑士到达[i,j]时的最大血量 int ans[1005][...

C++ 动态规划

2022-04-14

0 491