2023牛客暑期多校训练营5 – Nazrin the Greeeeeedy Mouse
题目链接 链接 题目大意 有n个物品，m个背包（体积从小到大给出），每个物品都有体积和价值，问m个背包能装下物品的最大价值是多少 题解 //dpi代表前i个背包存前r个物品时候能最大价值 每增加一个背包，就可以算出能存放物品的最大价值 转移方式为dpi = m…
Tag: 动态规划
AtCoder Beginner Contest 306 – D – Poisonous Full-Course
题目连接 链接 题目大意 有N个物品，0物品无毒，1物品有毒，你不能连续吃两次有毒的东西，吃完没毒的就会从前一种状态转移到现在吃的东西的状态，问你吃了的东西的总价值是多少。 题解 刚开始想的是双指针扫描，但是会有一个问题，如果前面选的是0，现在选了一个1，可能…
Educational Codeforces Round 109 (Rated for Div. 2) – D. Armchairs
题目链接 链接 题目大意 有n个座位，给一个数列，1代表有人，0代表没人，让所有人坐到其他没人的地方去，移动的花费是位置的差值，问你最少的花费是多少？ 题解 这道题第一个想法是把第一个人安排到自己前面所有空的地方，然后就有很多种安排方法，然后第二个人再安排到第…
2022年中国大学生程序设计竞赛女生专场 – I. 宠物对战
题目 题目链接 链接 题目大意 给你两个序列a,b每个序列中都有一些字符串，再给一个目标串s，问你这个s是否能由ababab或者babab类似这种形式组成，a表示a序列里面的字符串，b表示b里面的字符串。 题解 这个题目刚开始想直接凑就行，但是写的过程中想到一…
第十二届蓝桥杯省赛c/c++B组-括号序列
题目连接 题目链接 参考链接 参考链接 参考链接 题解 思路应该是计算出要加的左括号数目，然后再镜像字符串计算出需要添加右括号的数目，相乘即可。因为让他变成一个合法的字符串需要左括号的数目大于等于右括号的字符串，我们第一次可以计算出使得右括号一定有的匹配的方法…
D – Flip Cards
solution 这道题刚开始想的是所有的牌向上的那一面都不一样，然后就不知道怎么做了，后来读题是旁边的牌不一样就行。然后想的是这个鬼样子 f[1][0] = f[1][1] = 0; int p1 = q[1].x, p2 = q[1].y; for(int…
2023牛客寒假算法基础集训营5-L-小沙の抱团 hard
solution 因为找最小代价，所以初始化数组为最大 我们可以很快得知，最大状态也就是n的代价是固定的，最小代价不确定，所以我们从大到小推 我们用一维数组来dp,f[i]代表从n到达i时的代价。 那么转移方程就是f[i - i % v[j]] = min(f…
2023牛客寒假算法基础集训营4-清楚姐姐学01背包(Easy Version)
solution 题目大意，这道题的意思是背包大小是m,有n件物品，最优取的情况下，如果去掉这件物品，能产生的最大价值与不去掉时候的价值差多少。 首先使用01背包把最优情况算出来，然后去掉第i件物品，看看差值。 #include <algorithm&g…