#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; int dp[200010][2][2];// 1 biao 1 li void slove() { int n, k; std::cin >> n >> k; std::vector<int> a(n + 1), b(n + 1); for (int i = 1; i <= n; i++) std::cin >> a[i]; for (in...

贪心。要凑到最大的数量，让可以更改的位置的数值更改成为上一个离自己最近位置并且有数值的数-x。注意如果减到小于值域下限，我们可以直接更改为值域上限。这样做的目的是方便让后面的可更改位置产生贡献。凑最小的答案，就一直让可更改位置的数值更改为上一个值-x+1即可。 #include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; /*inline __int128 read(){ __int128 x = 0, f = 1; char ch = getchar()...

分层图最短路 链接：https://ac.nowcoder.com/acm/problem/236176 来源：牛客网 做法：直接去连边的话因为数据范围过大，所以会出现tle的现象，也有段错误的现象不知道是为什么，所以对于层与层之间的边，我们建立一个平台，同层的点到这个平台的距离为0，层与层之间的距离为c，那注意不能建立一个双向的平台，这样的话会出现一些不存在的边，所以要建立一个向上的路径和向下的路径分别为i+n和i+2n，之后就是特殊边正常连，然后跑dij即可，spfa可能为卡，但如果数据弱的话也是能过的。 //本题代码 #include<bits/stdc++.h> #defi...

链接：https://ac.nowcoder.com/acm/problem/236173 来源：牛客网 有一片群岛，总共有30001个岛屿，编号从0到30000，其中有 n 个宝藏在这些岛屿中。Kitayuta是一位宝藏猎人，他初始在0号岛屿上。为了获得宝藏，他按照如下规则经过这些岛屿：  ​ 他第一步从 0 号岛屿跨越 d 个岛屿到达 d 号岛屿。 ​ 接下来每一步，他只能前往编号更大的岛屿。并且，假设他前一步跨越了 x 个岛屿，那么他下一步只能跨越 y 个岛屿，其中 y∈{x−1,x,x+1} 且 y>=1 。如果下一步没有可以到达的岛屿，Kitayuta就会停止寻找宝藏。  假设...

货船 链接：https://ac.nowcoder.com/acm/problem/236172 来源：牛客网 有 n个货物，需要装入货船，第 i 个货物的重量是 wi 。货船的最大载重量是 A ，请问在不超过货船最大载重量的前提下，一次最多能运送多少重量的货物。 做法：一眼是01背包，但是无论是物品数量还是重量上限都超过了复杂度和空间复杂度，所以选择去优化背包，01背包其实就是选和不选的选择，非常适合用01字符串去表示，正好可以用stl中的bitset去解决，对于两个状态的字符串，如果这个物品不选，两个状态字符串是相同的，选择这个物品的话，就是多加了a【i】这么多的重量。对于字符串来说就是每...

链接：https://ac.nowcoder.com/acm/problem/235953 来源：牛客网 给你一个数组 a ，包含 n 个整数，你需要在数组 a 中选出不相交的 m 个连续子段，每个子段的长度至少为 1 。 定义每一个子段的贡献为子段内数字的和，你需要求出这 mmm 个子段的贡献之和的最大值是多少。 做法 对于选择一个数，我们可以接到当前第j个字段的尾巴，或者另外开一个字段，那么状态就在f【i-1】【j】+a【i】，f【k】【j-1】中产生，其中k表示以第k个位置为前第一个子段，那么当前选择的数为第j个子段，那么直接去找k的话就是n^ 2的复杂度，所以我们要维护一个数组去优化复...

链接：https://ac.nowcoder.com/acm/contest/84527/C 来源：牛客网 做法 暴力解法就是对于x的每一个位置去遍历最小和最大长度，那么复杂度肯定爆炸，我们先考虑一下最小长度和最大长度的关系，对于一个数来说，如果拓展的最小长度的最小值都小于x，那么最大也只能更小，所以只需要去看最小长度即可，那么就排除了最大长度的影响，那么就需要去优化循环向左向右的过程，我们定义两个数组l，r，l代表的含义为，第i个位置最多向左延展 l【i】个单位能保证i这个位置的元素最小，r数组同理，那么只需要用一个栈去模拟这个过程就能在on的复杂度内完成预处理，因为如果前面一个值小于后面的...

链接：https://ac.nowcoder.com/acm/problem/13230 来源：牛客网 输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。 需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可 做法 区间dp题，学到的一个点就是如果范围小就考虑开多维去存储，所以dp的思维就是两个串的左右端点，那么就有四种情况，当a串左右相等时，我们看一下缩小一点的a串是否是回...

孙悟空救师傅 链接：https://ac.nowcoder.com/acm/problem/235903 来源：牛客网 师傅又被妖怪抓走了。师傅被困的宫殿可以看作一个 n×nn\times nn×n 的由字符构成的矩阵，每一个字符表示一个房间。字符'K'表示孙悟空的起始位置，'T'表示师傅被困的位置，'S'表示有蛇的房间，'.'表示空房间，'#'表示无法进入的房间。矩阵中包含且仅包含一个'K'和一个'T'。 每分钟，孙悟空都可以上下左右移动一格，如果遇到蛇，打倒蛇需要额外花费一分钟，保证地图上最多有五个有蛇的房间。此外孙悟空还需要集齐所有种类的钥匙才能救出师傅。钥匙的种类以 1,2,...,m...

草药大师 链接：https://ac.nowcoder.com/acm/problem/235951 来源：牛客网 做法1 因为最大容量有1e9，我们需要剪掉一些情况，对于每次物品我们只能拿一次，那么，其实也是从尾开始跑，只不过我们把从最大容量改成最大能放进的容量，如果总容量减去这一个物品的容量比原先的塞进去的容量大，说明可以拿当前这一个物品，那么就去把这一个物品塞进背包就行。 //本题代码 #include<bits/stdc++.h> #define endl "\n" #define int long long //dont forget to check long long...

多重背包 链接：https://ac.nowcoder.com/acm/problem/235950 来源：牛客网 做法：适用于物品数量不是无限但又不止一个的背包问题，一开始想到的是将n个相同重量的物品当作n个不同的物品，但完全背包的复杂度已经汗流浃背，所以我们需要把这个重复的n进行优化，我们尽量去把2的幂作为一组进行打包，剩下的再作为一组打包，这样我们就能用我们构造的数去凑出任何一个1到n之间的数（拆位），那么之后就是经典01背包，这里用嵌套pair去存储（懒。 //本题代码 #include<bits/stdc++.h> #define endl "\n" #define ll...

合唱队形 链接：https://ac.nowcoder.com/acm/problem/16664 来源：牛客网 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 做法 要构造一个先递增后递减的序列，那么我们假设最优点为i，i其实就是最长上升子序列的结尾...

最长上升子序列 朴素dp （O(n^2)) //本题代码 #include<bits/stdc++.h> #define endl "\n" #define ll long long //dont forget to check long long //别写重变量名 //记得判越界 //别死磕 //处理字符串删掉关流 ll f[1000010]; void slove() { int n; std::cin>>n; std::vector<int> a(n+1); for(int i=1;i<=n;i++) std::cin>>a[i]; ...