11.1不能与DP好好相处题解

T1 不老的传说

题目大意:有n个石头环成一圈,每次染色能染1-k个连续石头,问多最少多少次能染成目标状态

这道题真的是各种既视感,环的话直接变成两倍的链就OK了,之后就是区间dp
\(f[i][j]\)表示(i,j)对i,j一段染色的最少次数

初始化就是\(f[i][j]=\begin{cases}1&i=j\\ 0&i>j\\ \infty&else\end{cases}\)

状态转移方程也很有既视感:\(f[i][j]=\begin{cases}min(f[i+1][j],f[i][j-1])&c[i]=c[j]\\min(f[i][z]+f[z+1][j]),z\in [i,j)&else\end{cases}\)


T2 多米诺骨牌

题目地址

题目要求的是上下翻转次数,首先要解决的是如何使得差值最小。很容易就这样想到,因为n块骨牌都可以任意翻转,那么肯定有一种摆放的方式顶行和底行之间的差值是最小的,找到这样的摆放方式就可以通过对比找到最小的翻转次数了,但是这样一个问题也不容易解决,因为总共有2n种摆放方式,不可能用计算机逐一检验对比。而且差值最小的摆放方式也不惟一,因此这样的方法是不可行的。

这个问题只能换一种方式来解决了。我们可以尝试一下动态规划的思想。之所以往这个方向去思考是因为我们发现,上面的方法行不通的主要原因是因为骨牌之间相互独立的,这个性质导致了摆放方式有很多,但是相互独立这个很重要的性质,如果能够加以利用,也许会为问题的解决带来很大的便利。

经过分析可以发現,如果做到了用最少的翻转次数达到差值是最小的摆放方式,此时任意一段骨牌都不可能用更少的方式得到同样的上下差值。更具体地说,前k块骨牌如果要达到某个差值(不一定最小),它将取决于前1块的翻转情况和第k块的翻转情况。如果确定了第k块的状态,那么前k-1块就必须要用最少的次数得到指定的差值了。据此,可以列出下面的递推公式:
假设gap[i][j]表示前i块骨牌要达到差值为j,需要的最少翻转次数。如果不能达到j的差值,那么令等于一个很大的数。


\(gap[i][j]=\begin{cases}min(gap[i-1][j-c[i]],gap[i-1][j+c[i]]+1),i\in [1,n] \\ \infty & else\end{cases}\)

其中c[i]为第i个骨牌上面-下面的值

初始条件是:


\(\begin{cases}g[0][0]=0\\g[0][j]=\infty\end{cases}\)

由于最多只有1000个骨牌,所以上下骨牌点数差值的总和的绝对值最大就是5000。所以,我们可以逐个骨牌来处理,把所有可以达到的值都计算出来,并记下是用了多少步而达到的,最后找出可以达到的最小值,并直接得到需要多少步达到。这样可以在规定时间内求得答案。

由于上下的差值在\([-5000,5000]\)之间,所以我们gap的第二维要开两倍空间,再往右偏移一倍空间


T3 文本压缩

题目大意:给你一个字符串和若干编码方式,输出编码后的最小长度

题目中的编码有个特点,就是无后效性,如abcdefgh前面的abcd如何编码跟后面的编码方法无关。
设函数\(F(s)\)表示文本s的压缩方式的编码长度,如题目例子:
\(F(a)=length("01")=2\)


\(F(abc)=length("0")=1\)


\(F(abcd)=4\)


\(F(bcd)=1\)


\(F(def)=2\)


\(F(ef)=2\)


设函数\(G(s)\)表示文本s的最短编码长度,有
\(G(a)=2\)


\(G(ab)=max\)


\(G(abc)=1\)


\(G(abcd)=4\)


\(G(abcde)=max\)


max表示不能编码
求\(G(abcdef)\)时,考虑其最后一个编码可能是def或ef,即abcdef=abc+def或abcd+ef

转移方程为:
\(G(s)=min(G(s_{11})+F(s_{12}),G(s_{21})+F(s_{22}),\cdots ,G(s_{n1})+F(s_{n2}))\)

其中\(s=s_{i1}+s_{i2},i\in[1,n]\)

@千柰dalao只开了1维数组,代码也比我的简洁


T4 瑞士轮

题目地址

dp专题出现排序算法真的是一点也不意外呢,当时还在努力想怎么dp,还好最后打了个暴力,没有被坑惨。
先上一个暴力:

STL受害者,用快排时间复杂度极高\(O(R(NlogN+N))\)
快排的快是针对随机数列来讲的(大部分情况下是这样),而这道题不同,每一轮过后,所有的胜利者的顺序不会变,所有的失败者的顺序也不会变,所以这个时候就要用归并排序了!!

归并排序和快排的区别(懒得打字了你们自己看图片吧)

归并排序

快排

看出来了吧,大家可以发现,归并排序每次的操作只针对相邻区间,或者说合并时是对相邻几个区间的操作,所以这符合只需要修改相邻几个分数的排布状况的题意。

然后就过了……
所以以后就算我用插入排序,用冒泡排序,我也不会用快排!!


T5 传球游戏

题目地址

其实这应该算是昨天的题目,在后面来一道水题


点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注