动归专题QAQ（两天创造的刷题记录哟！✿✿ヽ(°▽°)ノ✿✿）（未填坑）

1092 采药：由于没有限制开始时间和结束时间，01背包就好了

1095 开心的金明：01背包，无fuck说

1104 摆花：f[i][j]表示摆了i种花,第i种花摆了j种的方案数，乱转移0.0（感觉可以一维做？）

1124 方格取数：保证一个数取1次即可，f[i][j][k][l]表示第一个点走到(i,j)，第二个点走到(k,l)的最大收益，特判i==k&&j==l的情况即可

1137 排队买票：其实一开始对标解持怀疑态度，后面发现可以倒着推，保证不会出现第i个人买了两张票后第i+1个人也买了两张票的情况

1146 牛奶容器：将查询的加仑*16，然后暴力完全背包

1147 零件加工问题：写了两种做法：1、离散+按时间轴正着推 2、按结束时间排序，并按顺序二分查找第一个结尾<当前任务开头的节点，递推公式f[i]=max(f[i-1],f[find(a[i].s)]+a[i].v)

1148 乘法难题：暴力n^3区间DP，枚举断点即可，注意开区间

1150 最小中间和：区间DP，枚举断点，n^3

1164 传纸条：同方格取数，不过之后我会把n^3的解法写上来的（等我填坑哦0.0）

1166 找呀找呀找GF：二维背包问题，在当前答案比原来的答案更优时，同时更新时间和答案，在当前答案和原来的答案相同时，更新时间

1167 乘法游戏：与乘法难题相同，不解释

1168 公路乘车：简单完全背包，注意要刚好走n公里

1169 装箱问题：01背包，不解释

1176 奶牛的锻炼：f[i][j]表示第i分钟疲劳度为j的情况，每次从f[i-1][j-1]转移到f[i][j]，表示第i分钟跑，从f[i-j][j]转移到f[i][0],表示从i-j分钟到i分钟都休息。输出f[n][0]即可

1177 外星人的密码数字：暴力求最长不下降子序列。（之后我会开专题的QAQ）

1181 Bessie的体重问题：01背包，不解释

1187 尼克的任务

1198 最大的算式：这题有点恶心，我的做法是n^5区间DP。f[i][j][k]表示的是i到j这个区间内使用了k个乘号，注意不要从无用的情况转移到有用的情况，当然这题还有n^3的做法，不过我不会0.0

1199 字串距离：f[i][j]表示的是第一个字串前i位和第二个字串前j位的最小字串距离，初始化：f[i][0]=i*k,f[0][i]=i*k,f[i][j]=min(f[i][j-1]+k,f[i-1][j]+k,f[i-1][j-1]+abs(a[i]-b[j]))

1201 田忌赛马：这道题目需要一些思考能力，，其实我也是看hzwer的题解才会的┓( ´∀` )┏。首先我们首先想到的就是贪心，根据某个故事。。或者自己的推演，显然要么我们用当前最弱的马去对付齐王最强的马，要么用最强的马取赢过齐王最弱的马。于是我们就有了DP方程，f[i][j]表示的是前i次比赛用了j次最强的马，自然就用了i-j次最弱的马f[i][j]=max(f[i-1][j]+pd[n-(i-j)+1][i],f[i-1][j-1]+pd[j][i]),其中pd[i][j]表示的是田忌第i强的马和齐王第j强的马的胜负，平局为0，胜利为1，失败为-1

1202 最长不下降子序列：暴力裸题，不解释

1203 最长公共子序列：同1854

1208 沙子合并：将数列复制一遍，前缀和预处理，然后区间DP，DP预处理为f[i][i]=0,f[i][j]=min(f[i][k]+f[k+1][j])+sum[j]-sum[i-1](i<=k<j)

1210 金明的预算方案：这题有点意思，我们考虑把附属品和主件绑定，每次有4种方案：只取主件，取主件和第一个附件，取主件和第二个附件，取主件和两个附件，对于没有附件的主件，重要度和价格都为0，不影响答案

1215 合并傻子：同沙子合并，不解释

1220 合唱队形：从前到后求一遍最长上升子序列，从后到前求一遍最长上升子序列，然后合并答案就好了QAQ

1260 城市交通：记f[i]表示到达第i个城市的最短距离，n^2转移，枚举从哪个城市转移到该城市即可

1274 导弹问题1：同1276

1275 导弹问题2：同1276，子序列第一次到达最长的长度的时候break 输出方案

1276 导弹问题3：最长不上升子序列+最长上升子序列

1295 石子合并：将数列复制一份，然后n^3区间DP即可

1403 完全背包：题面就是算法。

1407 拦截导弹：同导弹问题3

1553 球的序列：将第二个序列变为第一个序列该数出现的位置，然后求最长上升子序列即可。

1721 01背包问题之1:01背包不解释

1854 最长公共子序列：将字符串转为数字数组，然后n^2DP,方程if(a[i]==b[j])f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1) else f[i][j]=max(f[i-1][j],f[i][j-1])

2140 面（noodle）：zxyer出的毒题，我们根据多重背包的性质拆分物品个数，然后跑01背包即可

巴特西

动归专题QAQ（两天创造的刷题记录哟！✿✿ヽ(°▽°)ノ✿✿）（未填坑）

最新文章

热门文章