Educational Codeforces Round 161 (Rated for Div. 2)
D
\(n\) 个怪物站成一个序列，有防御值和攻击值，每个怪物会受到来自左右两个怪兽的攻击，如果防御值小于两边攻击值之和则怪物死亡，从序列中移除，求每次移除的怪物。
暴力做第一次，发现每次可能被移除的怪物一定是上一次被移除的怪物的旁边。
E
构造长度小于等于 \(200\) 的序列 \(a\)，使得 \(a\) 中严格上升序列为 \(x\)，\(x\le10^{18}\)，包含空串。
首先构造出一组 \(1,2,3\dots n\)，发现序列数为 \(2^n\)（包含空串），如果在后面添加一个数 \(x\)，则序列数增加 \(2^(x-1)\)，将需要加入的数倒序添加就互不影响。
F
长度为 \(n\) 的序列 \(a\)，值域为 \([1,x]\)，每次选定一个区间，将这个区间全部赋值为任意一个在这个区间内没有出现过的数，求将整个区间赋为同一个值得最小操作数，\(n\le100,x\le100\)。
观察数据范围考虑 \(dp\)，令 \(f_{i,j,k}\) 为区间 \([i,j]\) 全部赋值为 \(k\) 的最小操作数，\(g_{i,j,k}\) 为区间 \([i,j]\) 赋值为不出现 \(k\) 的最小操作数。
可得状态转移方程：
\[f_{i,j,k}=f_{i,mid,k}+f_{mid+1,r,k} \]\[f_{i,j,k}=g_{i,j,k}+1 \]\[g_{i,j,k}=g_{i,mid,k}+g_{mid+1,r,k} \]\[g_{i,j,k}=g_{i,j,l}+1,(k\not = l) \]注意转移顺序，答案为 \(\minf_{1,n,i}\)
标签：操作数,mid,VP,区间,怪物,移除,序列 From： https://www.cnblogs.com/pointfish/p/18514287