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 接下来n-l行每行3个非负整数x,y,z，表示从存在一条从x到y权值为z的边。
> 1 [阅读全文]
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考... [阅读全文]
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 [阅读全文]
LOJ #539「LibreOJ NOIP Round #1」旅游路线
> T 城是一个旅游城市，具有n个景点和m条道路，所有景点编号为 1,2,...,n。每条道路连接这n个景区中的某两个景区，道路是单向通行的。每条道路都有一个长度。
> 为了方便旅游，每个景点都有一个加油站。第i个景点的加油站的费用为 pi,加油量为ci。若汽车在第i个景点加油，则需要花费pi元钱，之后车的油量将被加至油量上限与ci中的较小值。不过如果加... [阅读全文]
HDU 5603 D Game
MayFlyyh | DP | 2018-08-14
> 给一个公差集合{D}，再给N个数
> 1.在当前剩下的有序数组中选择X（X>=2) 个数字
> 2.检查1选择的X个数字是否构成等差数列，且公差∈{D} ;
> 3.如果2满足，删除这X个数字
> 4.重复1-3，直到不能删除更多数字
> 问最多可以删除多少个数字？
> N [阅读全文]
HDU 2476 String painter
MayFlyyh | DP | 2018-08-14
> 题意：给你一个由小写字母组成的串S，让你变成由小写字母组成的串F，你可以每次将一个区间变成任意一个小写字母，后来的操作可以覆盖原来的区间，求最小操作次数。
> |S| [阅读全文]