Z_L_G

分类

总结(8) 训练赛(3) 题解(60)

/ 注册

全部文章（共12篇）

算法入门-拦截导弹

题意有若干导弹，拦截系统只能拦高度降序的一组导弹，问一套系统最多拦截多少导弹，拦截全部导弹需要几套系统思路对于第一个问题，直接对整个序列跑一个最长递减子序列(LDS Longest-Decreasing-Subsequence) 对于第二个问题，正解是跑一个最长递增子序列(LIS)...

dp 最长递增子序列最长递减子序列

2025-05-06

0 10

算法入门-简单瞎搞题(分组背包+bitset优化)

题意有n个区间，从每个区间中取一个值求的种数思路分组背包，考虑前i组能不能凑出j，，其中k属于a[i] 双层枚举i,j,对于每一个j枚举区间，O(100*1000000*100)=O(1e10),过不了一点 for(int i=1;i<=n;i++){ fo...

dp 分组背包 bitset

2025-05-06

0 9

算法入门-[NOIP2004]合唱队形

题意共有n个人，每个人有身高，移除若干人，使得序列为{纯升序||纯降序||先升序后降序}，求最少的移除人数思路方法1：对于整个序列正着求一个最长上升子序列，反着求一个最长上升子序列，枚举每个位置两个序列和，最大的减一即为序列最长长度。方法2：维护一个二维dp数组，第二维记录当前元素属于...

dp 最长上升子序列

2025-05-06

0 8

算法入门-石子合并

题意给定n堆石子，成环放置，每堆石子有自己的重量，每次合并可以合并相邻的两堆，合并的得分是两堆石子重量和，求解把所有石子合并成一堆所得的最大得分和最小得分思路由于两堆石子是相邻的，所以每一次合成其实是对一个区间中的两堆的分界做考虑，下面按求最大得分考虑，如一共1~5，合并1~5的最后一次...

dp 区间dp

2025-05-04

0 14

算法入门-田忌赛马

题意齐王和田忌各有n匹马，田忌赢得200，输得-200，平局不得钱，请你安排顺序，解出可获得的最大钱数思路先将齐王和田忌的马降序排序贪心：对于齐王的第k匹马，田忌如果能赢就直接选当前第一匹马，如果不能赢就选择最后一匹马对于平局的情况，选择第一匹和最后一匹都有可能导致错误决策...

dp 区间dp

2025-05-03

0 18

算法入门-多重背包

题意种物品，每种物品有个，体积，价值，背包体积，求最大价值思路可以把每个物品直接放次，转化为01背包，大数据会TLE 打包-二进制优化：显然，每个数n可以拆成所有不大于它的二进制次方组合+剩余部分，如此便可表示从0~n，所以对每个进行拆分，从1开始，不断拆分，直到拆不出...

dp 多重背包

2025-05-01

0 18

算法入门-完全背包

题意 n种物品，每种物品有vol和val，背包体积为v，每种物品可以有任意多个，求背包最大价值和背包恰好装满最大价值思路 01背包变种，更新第二维时需要重复更新，改变循环方向即可 AC代码 #include<bits/stdc++.h> using namespace std;...

dp 完全背包

2025-05-01

0 13

算法入门-01背包

题意给定n个物品，每个物品由价值和体积，问装入体积为v的背包的最大价值和恰好装满的最大价值思路 01背包问题，对于每个物品考虑装和不装即可，如果不装\装不下，如果装则考虑装进来后的价值，对于每一个物品，在装和不装里取最大即可。注意到，n和val最大都可以取1000，二维数...

dp 01背包

2025-05-01

0 13

算法入门-最长公共子序列

题意给定两个字符串a,b,求a，b最长公共子串思路动态规划，最长的子串一定是由倒数第二长的子串加上两个串中一组相同的字符得来的即：（相同时）（不同） AC代码 #include<bits/stdc++.h> using namespace std; int f[5050][...

dp

2025-04-30

0 17

算法入门-[NOIP2001]装箱问题

题意 n个物品，箱子体积为v，装入物品后，箱子的最小剩余体积是多少思路动态规划对于每一个物品，考虑放或者不不放，观察体积即维护放入前i个物品能否满足体积为j (当前物品已经比需要的体积大了，放不进去) (当前物品可以放的进去，考虑放/不放) 特别的，本题有三种写法...

dp

2025-04-30

0 13