wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共4篇）

[bzoj4709][柠檬]

bzoj4709 思路首先，最优秀的分法一定是每段两端都是这一段中最多的那个，否则可以把不是的那个踢出去单独成段肯定会更优秀。然后就成了将这个序列分段，保证每段两端元素相同的最大收益和。用a[i]记录第i个位置上的数，用s[i]记录前i个元素中a[i]出现的次数。f[i]表示以前i个数的最...

动态规划dp 决策单调性

2018-10-08

0 425

[bzoj1563][诗人小g]

bzoj1563 思路首先考虑\(n^2\)的暴力dp，用sum[i]表示前i句话的长度总和。f[i]表示前i句话最小的不协调度之和。转移的时候考虑枚举前面的每个点，找到转移的最优秀的那个点。然后优化这个暴力。用一个队列存下当前个点之后的点中，哪个区间是从当前点转移更优秀(称为这个点的控制...

动态规划dp 决策单调性

2018-10-12

0 396

[bzoj1563][诗人小g]

bzoj1563 思路首先考虑\(n^2\)的暴力dp，用sum[i]表示前i句话的长度总和。f[i]表示前i句话最小的不协调度之和。转移的时候考虑枚举前面的每个点，找到转移的最优秀的那个点。然后优化这个暴力。用一个队列存下当前个点之后的点中，哪个区间是从当前点转移更优秀(称为这个点的控制...

动态规划dp 决策单调性

2018-10-12

0 483

[bzoj4709][柠檬]

bzoj4709 思路首先，最优秀的分法一定是每段两端都是这一段中最多的那个，否则可以把不是的那个踢出去单独成段肯定会更优秀。然后就成了将这个序列分段，保证每段两端元素相同的最大收益和。用a[i]记录第i个位置上的数，用s[i]记录前i个元素中a[i]出现的次数。f[i]表示以前i个数的最...

动态规划dp 决策单调性

2018-10-08

0 358