标签-区间dp

咕咕咕。
   题解    0 条评论
提高+/省选-
题意有 $N$ 个正整数,每次可以选相邻的相同的数合并,合并后得到的值为原数 $+1$ 。求合并后最大数的最大值。其中 $N\le 262144$ 。题解用 $f[i][j]$ 表示左端点为 $j$ ,能合并出 $i$ 这个数字的右端点的位置。显然 $i$ 是由 $i-1$ 转移过来的,所以我们要构造 $f[i-1][?]$ 。不妨考虑 $i+1$ ,在 $f[i][j]$ 这个右端点基础上...
   题解    0 条评论
提高+/省选-
题意一个序列 $S$ ,合并两个区间 $[l,x]$ 和 $[x,r]$ 对答案的贡献为 $(S_l+S_r)\times S_x$ 。先任取 $mid$ 将序列不断二分,直到每个区间只有一个元素后再合并。求答案的最大值,以及每阶段二分时取的 $mid$ 。按照阶段从小到大,每阶段内从左到右输出。其中序列的长度 $N\le 300$ 。题解显然区间dp,就是输出二分的方法有点麻烦。我最开始是...
   题解    0 条评论