瑜画

分类

题解(59)

/ 注册

全部文章（共59篇）

传球游戏题解

问题：n个人围成一个圈，从第一个人传球m次，每次能传给相邻的人，问有多少种方法经过m次传回给第一个人。思考：在第m次的时候传至第一个人手里，那么在m-1次的时候在第二个人或最后一个人手里。用dp[i][j]表示第j次传球，传到第i个人手里的情况有多少种。从而得到状态转移方程：dp[i][j]=dp[...

dp

2020-06-10

2 761

Rabbit的工作（1）题解

用一个二维数组dp[i][j]来表示工作i天，连续工作j天那么得到状态转移方程dp[i][j]=(dp[i-1][j-1])+j （如果当前字符为'1'）最终只要遍历dp数组，找到最长天数ans（并且它满足dp[i][j]<=K，即题目中说的总体力消耗不超过K） #include <bi...

dp

2020-06-10

0 752

CSL分苹果题解

将问题转化为wavator拿的苹果质量尽可能多，则变成一个容量为sum>>1的背包问题。由于题目要求的是质量尽可能多，那么w[i]等价于v[i]套用01背包模板，注意dp数组的大小至少要开到sum>>1 #include <bits/stdc++.h> using...

dp

2020-06-10

0 1018

方格取数题解

一开始的思路是这样的，安排两个人走，第一个人走的时候保证他拿的是最大化的，并且将走过的路全部置为0，再让第二个人走，保证最大，将两个人走过的数全部加起来，就是最后的答案，代码如下： #include <bits/stdc++.h> using namespace std; int a[1...

dp

2020-06-10

10 702

石子合并题解

设石子总数为n所求问题：1到n这些石子合并最少需要多少代价由于石子合并的顺序可以任意，我们将石子分为两个部分子问题：1到k这堆石子合并，k+1到n这堆石子合并，再把两堆石子合并，需要多少代价（1<=k<=n）那么便可以得到状态转移方程 dp[i][j]=min(dp[i][k]+dp[...

dp

2020-06-08

0 684

小木棍题解

思路：枚举可能的答案，由于题目要求的是求最小，从小到大开始枚举，最小可能是数组里最大的数，最大可能是数组里面所有数的总和。拼接木棍的过程使用dfs，每次拼接一定找未使用过的最大的木棍进行拼接做到以上，即可保证答案正确，但是速度还不够，需要进行剪枝。剪枝1：如果当前小木棍是拼接的整个木棍中的第一个...

2020-06-06

1 869

新建 Microsoft Office Word 文档题解

首先考虑New操作在没有delect的情况下得到的ID是依次加一的，用cnt来表示最新ID，有了delect操作后，ID会存在一个缺口，该缺口用优先队列的最小堆来完成，每次New弹出队顶元素，如果队列为空，则输出++cnt，否则弹出队顶并且输出。 #include <bits/stdc++.h...

2020-05-19

0 675

牛客算法周周练6 A~E题解

A题：思路：找规律吧，首先假设没有石墩，那么包括左岸在内，青蛙能够落脚的位置就有荷叶数+1（+1是包含左岸），青蛙按序号依次跳到右岸，那么ans=m+1现在有若干个石墩，给青蛙提供落脚点，令n=1，n=2，n=3……很快就能发现，ans成倍数增长，那么利用二进制的左移（<<）便可以快速得...

2020-05-13

0 636

牛客算法周周练5 C. 序列最小化题解

题目将n个数的某一种排列，经过若干次操作，变成同一个数。想要使操作数最少，那么第一次操作k个数，然后从第二次起操作额外的（k-1）个数和一个已经被操作过的数就可以了。实际操作次数跟数组里面的排列是怎么样的并没有关系，所以只是输入就好了。详细看代码。 #include <bits/stdc++....

2020-05-06

0 658