分类： 求解策略

附上一个讲的很好的链接https://blog.csdn.net/hao_zong_yin/article/details/79807322

第一感觉是类似矩阵连乘的那种操作，写完了才意识到复杂度会是2500^3，然后果断tle了（Final的题怎么会这么简单）。然后就没有什么太好的思路了。看了题解才有点明白。

这个题第一个难点在于，他又有分割又有合并，同时考虑这两种操作的话会很难设计状态转移，但是其实可以发现这两种操作的数量是有联系的，因为最初的堆数量是确定的，最后的堆数为1，所以分割和合并的数量关系可以确定出来，这样的话只需要算出来其中一种操作的数量就可以了，我这里考虑的是合并的次数w，经过推导可以得出最后答案ans与w的关系是 ans=2*w+n-1;（这个东西其实可以很简单的算出来：直接把每一摞盘子全到一起，总共的join次数为n-1，split次数为0；然后，每次在某一摞盘子内部进行一次split操作，则必然会在最后的结果中引入一次join操作，有一一对应的关系，因此可以推出来对于任意情况都有join次数==split次数+n-1）

第二个难点就是确定了要求合并的次数之后，如何进行dp。这里我们可以借鉴汉诺塔的思想，在考虑前i个（从小到大）盘子的时候，可以把大于i的盘子当成没有一样。而由于这里我关心的只是合并次数，所以不用考虑盘子的中间态（汉诺塔里盘子只能放在某个轴上，但是这里也可以放在地上），这样的话递推方程就会变得简单了。。。只需要使得dp[i][j]表示前i个盘子全放在第j堆上（想象一下这个画面）的最小操作数（这里要求第j堆必须有i这种盘子，说”这种”是因为离散化了），则转移的时候dp[i][j]一定是从dp[i-1][k]得来，其中1<=k<=n，而这时候又有不同的情况需要讨论 ：①j==k，这时候如果有i的堆的数量为1，那么就是第j堆这个（因为我们规定只有j堆有i的时候才往这里转移），那么他就不需要动，直接dp[i][j]=dp[i-1][j]；如果有i的堆的数量大于1，那就得先把j堆上的 (1到i-1) 这一坨移走，再把其他cnt[i]-1个i类盘子合并到j堆上，再把移走的 (1到i-1) 那一坨移回来（cnt[i]代表有多少堆含有i这个种类，可以预处理出来），所以总共增加的的操作数是cnt[i]-1+1=cnt[i]，也就是这里的方程为dp[i][j]=min(dp[i-1][k]+cnt[i]);     ②  j!=k  ，这时候好说，只需要考虑第k堆有没有i就可以了，如果有那就多了cnt[i]-1次操作，如果没有就多了cnt[i]-1+1次操作（注意约定是j堆一定有一个才能往那儿转移，所以除了那一堆里的那个i，还剩下cnt[i]-1个i）。

其他的也就是离散化的操作需要谨慎一点，我由于写错这个wa了两发。。。去重的时候先保留能保留的再去重！不然有可能导致数组扫描完了却没有存任何一个数（比如整个数组都是同一个数）

 

更：今天起床看了看2个月之前做的这个题，觉得当时还是naive，每次直接考虑只向含有第i种盘子的摞转移就好了，于是重写了第二种代码（其实核心思想完全一样的）

继续阅读“[DP][转化目标] UVa 1289 Stacking Plates”