Linyk
Linyk
全部文章
未归档
归档
标签
去牛客网
登录
/
注册
Linyk的博客
Dream it possible
全部文章
/ 未归档
(共4篇)
投票游戏
题目大意:有 n 个人参加投票游戏。 每个人会投支持票或者反对票,第 i 个人投支持票的概率是p[i] 。 选出k个人使平票的概率最大。 全部的输入数据满足: 2≤k≤n,k是偶数。 0≤pi≤1(1≤i≤n) n≤2000 思路:根据样例我们可以发现...
dp
2020-08-06
0
301
导弹拦截(升级版)JZOJ5354(提高)
Solution 第一问很明显,是动态规划 先把每个导弹排序后,f[i]表示拦截最后一颗导弹为i的最大拦截数 f[i]=max(f[i],f[j]+1) 那么对于第二问,就要换个思路 我们可以想,在系统拦截一个导弹i后,再拦截一个导弹j,点i向j连一条有向边 这样就形成了有向无环图(DA...
dp
2020-08-08
0
202
洛谷P1021 邮票面值设计 题解
首先,看到这题,大家肯定首先想到暴力+dfs吧! 可是这题暴力会超时; 好吧我们还是来认真思考下正解 思路应该是枚举出所有种类的邮票,最后判断一下,并记录最大值 暴搜,不行的话,可以剪枝? 1.使a数组保持单调递增,dfs中每次从a[k-1]+1开始搜索,以此来消除重复的搜索;(常规思路)...
dp
dfs
2020-11-05
0
288
[HAOI2006]数字序列 题解
Solution 题目链接 题目描述 现在我们有一个长度为 n的整数序列 a。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。 输入格式 第一行是一个整数,表示序列长度 n。 第二行有 n个整数,第 i个整数表示...
dp
2020-12-14
0
359