传送门 思路 记录这道题主要是为了记录二位前缀和的做题思路，毕竟CSP都遇见现题了，当时还只过了8个点... 其实前缀和也是一种形式的dp，这里借用LeetCode-304官方题解的图片，它画得很清晰了 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2021/04/1614650837-SAIiWg-1-1024x576.png 我们设dp[i][j]表示从矩阵左上角(0,0)到当前位置(i,j)的所有值之和，则不难得出图中的转移方程。减去dp[i-1][j-1]的原因是它在计算dp[i][j-1]+dp[i-1][j]中被计算了两次，要减掉多余的那一次。 这种思路在LeetCode周赛#225的T3中也有体现。 当我们对所有的(i,j)都算出前缀和后，用四重循环去依次枚举每一对左上角与右下角就行了。虽然纸面复杂度有O(n²* m²)，但每一个右下角一定在左下角后面，所以对右下角的枚举并没有严格的平方级复杂度，所以还是能把题混过去的。 代码 ```cpp int sum[110][110]; class Solution { public: int maxSumSubmatrix(vector>& mat, int k) { int m = mat.size(), n = mat[0].size(); for(int i = 1; i <= m; …
传送门 T1替换隐藏数字得到的最晚时间 思路 签到题，注意一些细节就行。 代码 ```cpp class Solution { public: string maximumTime(string time) { if (time[0] == '?' && time[1] >= '4' && time[1] != '?') time[0] = '1'; else if (time[0] == '?') time[0] = '2'; if (time[1] == '?' && time[0] == '2') …
传送门 题目大意 用2x1与2x2的小方块去填满一个2xn的长条形区域，问有多少种填法。 思路 很标准的dp。假设当前填到第i个位置，那么能继续往后推进的办法只有三种：竖着放一个2x1的方块，或者横着放两个2x1的方块、亦或者直接放一个2x2的方块。即，dp[n]的填法直接取决于dp[n-1]与dp[n-2]。 在n-1时只有一种方法可以填，所以dp[n-1]对dp[n]的贡献就是1*dp[n-1]；在n-2时有三种方法：竖着放俩、横着放俩、放块大的，因为“竖着放俩”的方法与n-1时重叠了，所以dp[n-2]对dp[n]的贡献就是dp[n-2]*2，最终得到转移方程： ```cpp dp[n] = dp[n-1] + dp[n-2] * 2; ``` 样例很善良的提醒了我们这题还是一个大数题目，所以用string来模拟大数加法，避免爆变量。 ```cpp string add(string a, string b) { //维护a长于b if(a.length() < b.length()) swap(a,b); //进位值 int up = 0; //自尾向头计算 for(int i = a.length() - 1, j = b.length() - 1; …
传送门 t1 存在连续三个奇数的数组 签到题，直接O(n²)遍历就能过。 ```cpp class Solution { public: bool threeConsecutiveOdds(vector& arr) { const int n = arr.size(); if(n < 3) return false; for(int i = 2; i < n; i++) { int cnt = 0; for(int j = i-2; j <= i; j++) …
传送门 题目大意 定义S(x)为x数位和，给出N,满足S(A)>S(B),1≤A≤B≤N的A,B组数。 ```cpp #include using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll dp[110][1810][2][2]; char c[910]; int l; ll dfs( int x, int y, int u, int v ) { ll res = 0, a, …
动态规划是一个非常非常重要的算法。众所周知LeetCode周赛中十hard九dp，接触算法那么多年，动态规划始终没有做到完全的掌握，趁着这月LeetCode周赛的主题是dp，也争取完全掌握这门 算法。 内容会不定期更新，初步目标二十道，由易到难。 LeetCode-121:买卖股票的最佳时机 传送门 lc上的dp老题了，其实它只是借用了dp思想而已，和传统的dp有一点点差别。 首先考虑暴力做法。题意不难理解，找出数组中差值最大的两个数，输出他们的差值，要求较小数的下标要小于较大数。那么可以很简洁的写出一个直译： ```cpp class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int ans = 0; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) ans = max(prices[j]-prices[i], ans); return …
传送门→ 很经典的DP。设dp[i]为走到第i级台阶的总方案数，那么显然可以得到状态转移方程：dp[i]=dp[i-1]+dp[i-2]。因为每一步能走一级或者两级台阶。 初始化dp[1]=1,dp[2]=2，然后跑循环就行了。 ```cpp class Solution { public: int climbStairs(int n) { int dp[100]; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]; return dp[n]; } }; ```
传送门→ 这双周赛改成贪心赛算了，fo了。 A拥有糖果最多的孩子 贪心+暴力。两重循环外层枚举每一个小朋友，内层去找当前的最大糖果数量。如果当前小朋友的糖加上额外给的能大于等于这个最大值就push一个1进去，否则push一个0。 ```cpp class Solution { public: vector kidsWithCandies(vector& candies, int extraCandies) { vector ans; int n = candies.size(); for(int i = 0; i < n; i++) { int maxn = 0; for(int j = 0; j < n; j++) if(i == j) …
A有趣的数字 我们称一个数是质数，而且数位中出现了 5 的数字是有趣的。例如 5,59,457 都是有趣的，而 15,7 不是。求 1 到 100000 中有趣的数的个数。 没啥好说的，就硬来。先用筛法打出素数表，再用check函数确认数位里是否含5。时间复杂度肯定是不优的，但填空题嘛能解出来就是AC。最后答案是3282. ```cpp #include #include #include #include #define get(x) scanf("%d", &x;) #define lget(x) scanf("%lld", &x;) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for (int a = b; a <= c; a++) using namespace std; typedef long long ll; const int …
传送门 题面 我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。 [图片缺失] 原图：http://lx.lanqiao.cn/RequireFile.do?fid=FaHtNHE3 输入 第一行两个数n和m，表示作品数和木板数；第二行n个数Hi，表示从左到右第i个作品的高度。 输出 一行一个数ans表示答案。 样例数据 样例输入 5 2 4 2 3 5 4 样例输出 22 数据规模 对于30%的数据：1<=n，m<=10；对于100%的数据：1<=n，m<=100，1<=Hi<=10000。 思路 题面意思转述一下就是：将若干幅矩形的画作通过不同的相邻组合方式，在用尽m块木板的情况下，使得覆盖它们的面积最小。显然这个面积由被覆盖区间中最高的画作来决定，所以需要设hmax[i][j]为hi~hj中画的最大高度。 设 dp[i][j]为用j块板子覆盖前i幅画的最小面积，记k为在dp[i][j]状态下还剩的板子数量。可以得到状态转移方程： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020031713184378-1024x61.png 关于初始状态的确定，这里在求最小值，所以dp初始化为INF。如果用一块板子来覆盖前i幅画，显然面积只能为i·hmax[1][i]，所以dp[i][1]初始化为 i·hmax[1][i] 。 ```cpp #include #include …