CF1452D Radio Towers
MayFlyyh | DP | 2020-11-21
CF1452D Radio Towers
有 $n +2$ 个点，编号从 $0$ 开始，线性排列，从点 $1$点 $n$ 每个点被取到的概率为$ \large \frac{1}{2}$ ，求能产生合法覆盖的概率对 $998244353$ 取模。
每个点若向左覆盖了 $x$个点，则他必须同时向右覆盖 $x$ 个点，即覆盖范围 $[i - x,i + x]$ ( $x$ 由自己决定)
当每个点仅被覆盖一次，且点 $0$ 和点 $n-1$ ... [阅读全文]
CF1437E Make It Increasing
MayFlyyh | DP | 2020-11-03
CF1437E Make It Increasing
给你一个数列 a ,一个集合 b , 对于每个 b 中的元素x， $a_x$ 不能修改，其他都可以修改，问最少多少次可以将 a 修改为严格单调递增的。如果不存在，输出 -1 。
a 中的所有元素在任意时刻必须都是整数。
首先先判断是否合法，要保证两个不能改变的数$a_{b_i}$和$a_{b_{i+1}}$之间够不够放下$b_{i+1}-b_i$个数
i... [阅读全文]
Luogu P2569 [SCOI2010]股票交易
MayFlyyh | DP | 2018-12-19
[SCOI2010]股票交易
最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。 通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购... [阅读全文]
51nod 1294 修改数组
MayFlyyh | DP | 2018-10-23
题意：给出一个整数数组A，你可以将任何一个数修改为任意一个正整数，最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数？
n<=100000,0<=a[i]<=10^9
因为新生成的数列必须是正整数，那么第一个数必至少为1，同样，每个数在新生成的数列中至少应该为下标。。
那么除去那些值小于自身下标的，剩下的数从取值方面没... [阅读全文]
BZOJ 2091 [Poi2010]The Minima Game
MayFlyyh | DP | 2018-09-20
Description
给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。
每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。
在这样的情况下，最终A的得分减去B的得分为多少。
Input
第一行一个正整数N (N <= 1,000,000)，第二行N个正整数（不超过10^9）。
... [阅读全文]
BZOJ 3875 [Ahoi2014&Jsoi2014]骑士游戏
MayFlyyh | DP | 2018-09-20
Description
【故事背景】
长期的宅男生活中，JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会
扮演一个英勇的骑士，用他手中的长剑去杀死入侵村庄的怪兽。
【问题描述】
在这个游戏中，JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻
击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸... [阅读全文]
BZOJ 4987 Tree
MayFlyyh | DP | 2018-09-18
从前有棵树。
找出K个点A1，A2，…，Ak。
使得$∑dis(A_i,A_i+1),(1<=i<=K-1)$最小。
第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。
接下来n-l行每行3个非负整数x,y,z，表示从存在一条从x到y权值为z的边。
1<=k<=n。
l<x,y<=n
1<=z<=10^5
n <= 3000
好题是好题。。完全没看懂题意... [阅读全文]
BZOJ 1584 [Usaco2009 Mar]Cleaning Up 打扫卫生
MayFlyyh | DP | 2018-08-16
有N头奶牛，每头那牛都有一个标号Pi，1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有k个不同的数，那不河蟹度为$k*k$。那总的不河蟹度就是所有段的不河蟹度的总和。
求最小不和谐度哇
考虑如果把每一只牛都作为1段，那么不和谐度为n，所以每一段的种类不可能超过$\sqr... [阅读全文]
BZOJ 4033 [HAOI2015]树上染色
MayFlyyh | DP | 2018-08-16
有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并
将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
设dp[i][j]为以i为子树，染j个黑点对全局的贡献
$dp[i][j]=dp[i][j-t]+dp[e][t]+cost$
cost考虑i的儿... [阅读全文]
HDU 5603 D Game
MayFlyyh | DP | 2018-08-16
给一个公差集合{D}，再给N个数
1.在当前剩下的有序数组中选择X（X>=2) 个数字
2.检查1选择的X个数字是否构成等差数列，且公差∈{D} ;
3.如果2满足，删除这X个数字
4.重复1-3，直到不能删除更多数字
问最多可以删除多少个数字？
N<=300
一眼看去十分复杂，难点1在检验一串数字是否为等差数列，难点2在删除一段数字... [阅读全文]