多重背包 链接：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++) st...

传球游戏 链接：https://ac.nowcoder.com/acm/problem/16619 来源：牛客网 上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。 游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且...

链接：https://ac.nowcoder.com/acm/problem/15665 来源：牛客网 小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。 小明只能向上下左右相邻的格子移动，每移动一次花费1秒。 有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下...

链接：https://ac.nowcoder.com/acm/problem/235247 来源：牛客网 Sramoc(K,M) 表示用数字0,1,2,3,4,...,k−10,1,2,3,4,...,k-10,1,2,3,4,...,k−1组成的自然数中能被M整除的最小数。给定K,MK,MK,M2≤K≤10,1≤M≤10002\leq K\leq 10,1\leq M\leq 10002≤K≤10,1≤M≤1000，求Sramoc(K,M)Sramoc(K ,M)Sramoc(K,M)。例如K=2,M=7K=2,M=7K=2,M=7的时候,Sramoc(2,7)=1001Sramoc(2 ,...

链接：https://ac.nowcoder.com/acm/problem/207759 来源：牛客网 考古队员发现，牛市之所以会有那么多古老遗迹，是因为牛市曾经遭遇过一场几乎毁灭了他的流星雨，那场流星雨中流星体积很大，无法在撞击到地面前燃烧完，所以对牛市几乎造成了毁灭性的打击，但是，我们牛市的先民也是很厉害的，他们对于流星雨的预报虽然没有提前太多的时间但是详细到了每颗流星坠落的位置，所以虽然牛市在那一场流星雨之后满目疮痍，但是牛市的百姓大多都存活了下来。因为自然环境受到了巨大的破坏，他们记录下了这段历史搬到其他的地方繁衍生息，很多代人之后，牛市的自然环境有了恢复，他们后代中的一些人又搬了回...

链接：https://ac.nowcoder.com/acm/problem/201613 来源：牛客网 Nancy喜欢吃果冻！ Nancy钻进了一个n×n×nn \times n \times nn×n×n的果冻里，她想从(1,1,1)一路上、下、左、右、前、后六个方向吃到(n,n,n)。 但果冻毕竟是有许多口味的，标记为*的口味是Nancy不愿意吃的，其余的果冻均标记为.。 Nancy不想吃坏肚子，于是她想尽可能少的吃果冻。 下面给出果冻的情况，请你帮忙计算一下她能吃多少块果冻叭！ 做法：误打误撞写了个三维bfs模板题，也是调了有一会，感觉大佬的题解有点难懂，在结构体装一个当前状态的步数感...