容易发现最终序列所有数字的相对顺序不变，一个数字可能的覆盖范围由两边第一个比它大的数决定，且若不考虑次数限制所有这样的序列都可以变换得到。对于一个序列，其需要的最少变换次数显然就是覆盖了别的位置的数的个数。于是设f[i][j][k][0/1]为第i位填了第j个数时以最优策略操作了k次，第i-1为是否填j时，变换方案数。转移考虑这一步填j是否要额外增加操作次数即可。暴力dpO(n 容易发现最终序列所有数字的相对顺序不变，一个数字可能的覆盖范围由两边第一个比它大的数决定，且
阅读背景：
BZOJ4621 Tc605（动态规划）
来源：互联网
分享到：
