题目链接
题意
- 有一排有色石头,然后把相同颜色排在一起
- 能做的操作是交换相邻的石头
- 求最少的操作次数
- n $\in$ [2,4⋅$10^5$]
- $a_i$ $\in$ [1,20]
题解
总体思路
- 看到 $a_i$ $\in$ [1,20],所以算法从 $a_i$ 下手,也就是说对每种颜色下手
- 通过
cnt[i][j]
计算出把所有的i颜色的放到j颜色前面需要做的这两种颜色之间的交换次数 - 然后用子集dp来递推出最后的答案,就是说一开始是0种颜色之间的关系,然后慢慢得加入各种颜色进去
- 每次加入一种颜色的时候就是把新的颜色放到最后面,然后这样子一直求出所有颜色放入后的最优决策,而且不重不漏!
- 子集dp:
- 这里的状态就是,dp[$i_{1到1<<20-1}$]
- 数字i的每一个0,1字符代表着此状态下某种颜色是否存在
dp[i]
就是状态i的swap数量- 就是枚举所有的状态,然后向着添加各种尚未存在的颜色放到最后面的操作来进行dp转移,从子集推向更大的状态集
为什么这样可以不重不漏?
- 因为我们for(1<<20-1) for(20) 的双重循环,就是已经枚举了所有的已经存在的颜色状态,然后把新的颜色放到最后的方案!
- 比如红黄蓝,在 红黄 状态时会有 加入蓝 (蓝在最后),同理也有 红蓝 + 黄,黄蓝 + 红! 这样就达到了不重不漏
英文的tutorial
AC代码(tutorial版)
1 |
|
AC代码(简洁版)
1 |
|
单词学习
exponential 指数的
每天一句叨叨
自然界没风风雨雨,大地就不会春华秋实。