Loceaner

未归档

学习笔记(12) 日常犯二(8) 题解(1)

/ 注册

全部文章 / 未归档（共10篇）

洛谷 P1091 合唱队形

\[传送门在这里呀\] 题目描述 \(N\)位同学站成一排，音乐老师要请其中的\((N-K)\)位同学出列，使得剩下的\(K\)位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为\(1,2,…,K\)，他们的身高分别为\(T_1,T_2,…,T_K\)，则他们...

洛谷动态规划

2019-04-26

0 567

洛谷 P1439 【模板】最长公共子序列

\[传送门啦\] 题目描述给出\(1-n\)的两个排列\(P1\)和\(P2\)，求它们的最长公共子序列。输入输出格式输入格式：第一行是一个数\(n\)，接下来两行，每行为\(n\)个数，为自然数\(1-n\)的一个排列。输出格式：一个数，即最长公共子序列的...

洛谷动态规划

2019-04-27

0 396

洛谷 P1049 装箱问题

\[传送门在这呢！！\] 题目描述有一个箱子容量为\(V\)（正整数，\(0 \le V \le 20000\)），同时有\(n\)个物品（\(0<n \le 30\)，每个物品有一个体积（正整数）。要求\(n\)个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入...

洛谷背包动态规划

2019-04-27

0 498

一本通 1285：最大上升子序列和

我是传送门【题目描述】一个数的序列\(bi\)，当\(b_1<b_2<...<b_S\)的时候，我们称这个序列是上升的。对于给定的一个序列\((a1,a2,...,aN)\)，我们可以得到一些上升的子序列\((a_{i1},a_{i2},...,a_{iK})\)，这里\(...

一本通动态规划

2019-04-27

0 433

洛谷 P1164 小A点菜

传送门！题目背景 uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。 uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。题目描述不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩\(M\)元\((M \le 10000)\)。餐...

洛谷背包动态规划

2019-05-05

0 466

洛谷 P1057 传球游戏

传送门我在下面哦~~ I'm here 思路比较基础的DP,用\(dp[i][j]\)来表示第j轮传到i个人有几种办法,然后到传到一个人只有从右边或者从左边, 所以状态转移方程为:\(dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1]\) 有几种特殊情况:当到第一个...

洛谷动态规划

2019-05-09

1 410

洛谷 P1910 L国的战斗之间谍

洛谷 P1910 L国的战斗之间谍传送门思路二维背包模板题三维肯定会爆掉，所以换二维代码 #include <bits/stdc++.h> #define N 1111 using namespace std; int n,m,x; int a,b,c; int f...

洛谷背包动态规划

2019-05-23

1 398

洛谷 P4290 [HAOI2008]玩具取名

传送门思路博客半年没更新了，来更新个博文吧在\(dsr\)聚聚博客的帮助下，我用半个上午和一个中午的时间苟延残喘地完成了这道题先是读题目读大半天，最后连个样例都看不懂之后又是想思路，实在想不出来，便去看了\(dsr\)学长的博客，发现是一道区间\(DP\)题我们用\(f[i]...

洛谷动态规划

2019-09-02

1 496

洛谷 P1002 过河卒

传送门思路菜鸡小学生\(loceaner\)现在才知道过河卒怎么做…… 首先我们把马的控制点全部标记一下（顺便判断一下边界，后面就不用判了）然后用\(DP\)来做，需要注意的是如果\(f[0][0]\)也是妈的控制点的话，就没法到达\(B\)点了，所以\((0,0)\)不是控制点才可以...

洛谷动态规划

2019-09-02

1 429

洛谷 P1352 没有上司的舞会

传送门思路一道入门的简单的树形\(DP\)题我们用\(is\)数组来表示这个点是不是根节点如果他有上司，就绝对不是根节点了因为这是一棵树，所以只会有一个人没有上司，而他就是根节点然后考虑如何进行\(DP\)，我们用\(f[x][0/1]\)表示只考虑以\(x\)点为根的子树，且\(x...

洛谷动态规划

2019-10-14

1 546