ComplexPug

未归档

做题记录(1)

/ 注册

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

bzoj2086: [Poi2010]Blocks DP，单调栈

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2086 思路这就有点妙了题目意思就是让你求平均数>=k的最长序列先求出a[i]-k的前缀和就是求sum[i]-sum[j]>=0的最大i-j 当\(j<=k&...

单调栈 DP

2019-02-24

0 482

CF767C 记录错误

链接 https://codeforces.com/contest/767/problem/C 思路之所以把这个题放进来，是因为要记录错误情况不止一种所以答案存储就是>=2了代码 #include <iostream> #include <cstdio>...

DP

2019-02-26

0 417

bzoj2298: [HAOI2011]problem a DP

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2298 思路把一个人的话转化为区间的线段，显然是\([a_{i},n-b_{i}]\) 然后找最大的不相交，不覆盖的最多线段数量注意是有重复的数字，所以不是单纯的线段覆盖 f[i]=m...

DP

2019-02-21

0 530

bozoj3131: [Sdoi2013]淘金数位dp

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3131 思路 1. 函数值的素因子只有2、3、5、7 由他们组成的状态不多，爆搜的时候即使搜不对也没关系，我们只是缩小范围而已所以不要管呢么多，搜到几万就差不多了，包含有可能的就行 ...

数位DP DP

2019-02-21

0 402

bzoj4008: [HNOI2015]亚瑟王 dp

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=4008 思路神仙啊 \(f[i][j]表示第i个点有j次机会(不管成功与否)\) \(f[i][j]=f[i-1][j]*(1-p[i-1])^p\) 第i-1个j次都失败 \(f[...

DP

2019-02-22

0 508

CF113D 高斯消元、dp

题目链接 https://codeforces.com/contest/113/problem/D 思路 \(k[i]=\frac{1-p[i]}{ru[i]}\) f[i][j]表示经过i和j的次数的期望=概率 \(f[i][j]=p[i]*p[j]*f[i][j]\) \(+k[i]*p[...

DP 数论-高斯消元

2019-02-22

0 459

loj#2510. 「AHOI / HNOI2018」道路记忆化，dp

题目链接 https://loj.ac/problem/2510 思路 f[i][a][b]表示到i时，公路个数a,铁路个数b 记忆化复杂度=状态数=\(nlog^2n\) 代码 #include <bits/stdc++.h> #define ll long long us...

记忆化 DP

2019-02-24

0 642

bzoj1566: [NOI2009]管道取珠 DP

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1566 思路 n个球，第i个球颜色为ai，对于颜色j，对答案的贡献为颜色为j的球的个数的平方 k^2=(1+1+1+..+1)*(1+1++1+..+1) for (i=1; i<...

DP 转化

2019-02-24

0 556

3900: 交换茸角

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3900 思路状态压缩，f[i]表示只包含i中的所有元素的最小代价所有元素排序后两两配对都不能满足，就是inf 其他的，一定小于等于元素个数-1 orz wxy 收获 1，知道自己啥...

DP 状态压缩

2019-02-26

0 516

[NOI1995]石子合并四边形不等式优化

链接 https://www.luogu.org/problemnew/show/P1880 思路总之就是很牛逼的四边形不等式优化复杂度\(O(n^2)\) 代码 #include <iostream> #include <cstdio> #include &l...

四边形不等式优化 DP

2019-02-26

0 550