多重部分和问题
//多重部分和问题
int MultipartSum(int a[], int m[], int n, int k){
int dp[n + 1];
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j <=……继续阅读 »
yanzexi
1年前 (2023-11-04) 209浏览 0评论
0个赞
计数类$DP$：整数划分
//计数 DP：整数划分（完全背包问题思路）
int IntegerPartitioning(int n, int M){
int DP[n + 1];
DP[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
……继续阅读 »
yanzexi
1年前 (2023-11-03) 246浏览 0评论
0个赞
线性$DP$：数字三角形
//线性 DP：数字三角形
int Triangle(int n, int a[][100]){
int DP[n + 1][n + 1];
memset(DP, -0x3f, sizeof(DP));
DP[1][1] = a[1][1];
for(int i = 2; i <= n; i++){
for(int j ……继续阅读 »
yanzexi
1年前 (2023-11-01) 254浏览 0评论
0个赞
此部分代码大都是伪码；
01 背包
//01 背包
void z_o_bag(int n, int m, int w[], int v[]){
int DP[n + 1][m + 1];
memset(DP, 0, sizeof(DP));
for(int i = 1; i <= n; i++){
……继续阅读 »
yanzexi
1年前 (2023-10-31) 255浏览 0评论
0个赞
算法
算法：是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列，一般情况下应当具备以下要素：
输入与输出 I/O
输入：待计算问题的任一实例，都需要以某种方式交给对应的算法，对所求解问题特定实例的这种描述统称为输入。
输出：经计算和处理之后得到的信息，即针对输入问题实例的答案，称作输出。
基本操作、确定性和可行性
确定性和可行性是指算法可描述为由若干语义明确的基本操作组成的指令序列，且每一基本……继续阅读 »
yanzexi
2年前 (2023-08-28) 304浏览 0评论
2个赞
今天血崩，基本没有独立写完的 orz，太菜了还是要要多练练。
P8649 [蓝桥杯 2017 省 B] k 倍区间
题目传送门
一开始就暴力前缀和，结果果然没有全部拿下，剪了一会枝结果并没有什么卵用 orz。出去逛了一圈题解学到了同余的思想，wr 我怎么想不到捏，还是挺好理解……继续阅读 »
yanzexi
2年前 (2023-03-08) 363浏览 0评论
0个赞
题目描述
题目传送门
你有一架天平和 NN 个砝码, 这 NN 个砝码重量依次是 W_{1}, W_{2} ,⋯,W_{N}。 请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
输入格式：
&nbs……继续阅读 »
yanzexi
2年前 (2023-03-07) 358浏览 0评论
0个赞
题目描述
题目传送门
在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者向下走。问有多少种方案？
……继续阅读 »
yanzexi
2年前 (2023-03-07) 266浏览 0评论
0个赞
题目传送门
本题思路很简单，只要找到水容量之和最大的区间即可，注意区间长度为 k+1 不是 k，简单写个前缀和搞定！
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using names……继续阅读 »
yanzexi
2年前 (2023-03-07) 340浏览 0评论
0个赞
本题纯暴力的复杂度过高，首先枚举左上顶点和右下顶点的复杂度就达到了 O(n^4)级别的复杂度，再计算子矩阵的和，复杂度又达到了 O(n^6)，显然是非常容易爆掉的。
优化以后的思路大概就是前缀和+二分查找优化，这样可以降到 O(n^3logn)的复杂度，首先构建二维前缀和矩阵，这样可以用 O(1)级别的复杂度来计算子矩阵的和。其次我们考虑对枚举子矩阵的优化，首先枚举行的组合是不可避免的，左列的复杂度也不可避免，但是……继续阅读 »
yanzexi
2年前 (2023-03-06) 349浏览 0评论
0个赞
![P8742 [蓝桥杯 2021 省 AB] 砝码称重——炎泽汐 の Blog](https://www.xn--920a971a.top/wp-content/themes/Git-alpha/timthumb.php?src=https://www.xn--920a971a.top/wp-content/uploads/2023/03/2023030714311841.png&h=160&w=260&q=90&zc=1&ct=1)
![P8707 [蓝桥杯 2020 省 AB1] 走方格——炎泽汐 の Blog](https://www.xn--920a971a.top/wp-content/themes/Git-alpha/timthumb.php?src=https://www.xn--920a971a.top/wp-content/uploads/2023/03/2023030714280538.png&h=160&w=260&q=90&zc=1&ct=1)
![[NOI Online #3 提高组] 水壶——炎泽汐 の Blog](https://www.xn--920a971a.top/wp-content/themes/Git-alpha/timthumb.php?src=https://www.xn--920a971a.top/wp-content/uploads/2023/03/2023030714191584.png&h=160&w=260&q=90&zc=1&ct=1)
![[蓝桥杯 2022 省 B] 统计子矩阵——炎泽汐の Blog](https://www.xn--920a971a.top/wp-content/themes/Git-alpha/timthumb.php?src=https://www.xn--920a971a.top/wp-content/uploads/2023/03/2023030614072920.png&h=160&w=260&q=90&zc=1&ct=1)