这里是关于区间型动态规划的题目以及程序
区间型动态规划
石子归并
题目描述 Description
有$n$堆石子排成一列,每堆石子有一个重量$w[i]$, 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和$w[i]+w[i+1]$。问安排怎样的合并顺序,能够使得总合并代价达到最小。
要求$n$个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入描述 Input Description
第一行一个整数$n(n \leq 100)$
第二行$n$个整数$w_1,w_2…w_n (w_i \leq 100)$
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
数据范围及提示 Data Size & Hint
无
Consideration 想法
状态方程:$ dp [ i ] [ j ] $表示把区间$[i,j]$合并所需要的最小花费.
状态转移方程:$dp[i][j]=dp[i][k]+dp[k+1][j]+(w[i]+w[i+1]+…+w[j-1]+w[j])$.
可见先要求出小区间,才能求大区间.
有两种做法:
1.先求出所有长度为$2$的区间,再求出所有长度为$3$的区间…最后求出长度为$n$的区间.
2.先求出区间右端点是$2$的区间,再求出区间右端点时$3$的区间…最后求出区间右端点是$n$的区间.
注意:
1.解法1中的小区间都是求过的,可以直接使用.但是注意初始值$dp[i][j]=INF$.画个图可以看出来$k$的取值范围是$[i,j)$.
2.解法2中在求解以$j$为区间右端点的区间时,区间右端点小于$j$的区间都可以直接使用.如果求区间$[i,j]$,那么要用到区间$[i,k]$和$[k+1,j]$,其中$[i,k]$可以直接使用,而要使用$[k+1,j]$就必须在求解$[i,j]$之前先求解$[k+1,j]$,又因为$k+1>i$,所以在求解区间右端点为$j$的区间时,左端点要从右向左枚举.
The Code Of My Program AC代码
解法 1
1 | /********************* |
解法 2
1 | /********************* |
能量项链
题目描述 Description
在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有$N$颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为$m$,尾标记为$r$,后一颗能量珠的头标记为$r$,尾标记为$n$,则聚合后释放的能量为$ m * r * n $ (Mars单位),新产生的珠子的头标记为$m$,尾标记为$n$。
需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。
例如:设$N=4$,$4$颗珠子的头标记与尾标记依次为$(2,3) (3,5) (5,10) (10,2)$。我们用记号$⊕$表示两颗珠子的聚合操作,$(j⊕k)$表示第$j,k$两颗珠子聚合后所释放的能量。则第$4、1$两颗珠子聚合后释放的能量为:
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
输入描述 Input Description
第一行是一个正整数$N(4 \leq N \leq 100)$,表示项链上珠子的个数。第二行是$N$个用空格隔开的正整数,所有的数均不超过$1000$。第$i$个数为第$i$颗珠子的头标记$(1 \leq i \leq N)$,当$ i < N $时,第$i$颗珠子的尾标记应该等于第$i+1$颗珠子的头标记。第$N$颗珠子的尾标记应该等于第$1$颗珠子的头标记。
至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。
输出描述 Output Description
只有一行,是一个正整数$E(E \leq 2.1 * 10^9)$,为一个最优聚合顺序所释放的总能量。
样例输入 Sample Input
4
2 3 5 10
样例输出 Sample Output
710
数据范围及提示 Data Size & Hint
无
Consideration 想法
$d[i][j]$表示合并区间$[i,j]$得到的最大能量。
$ d [ i ] [ j ] = max(d [ i ] [ k ] + d [ k+1 ] [ j ] + a[i] * a[k+1] * a[j+1]) $
其中$a[i]$表示第$i$颗珠子的头标记(注意搞清楚这几个头尾的关系,差点被搞晕)
假设以$1$号珠子为起点,则最大能量为$d[1][n]$。
现在没说起点是哪个,最直接想到的方法是枚举。可是,跑一次的复杂度是$O(n^3)$,算上枚举的话就是$O(n^4)$,对于$n=100$,很有可能会$TLE$,得有个改进的方法。(天梯上面的数据没卡时间,我枚举法交上去居然A了)
假设有五颗珠子,编号分别是$1 \; 2 \; 3 \; 4 \; 5$,则以$2$为起点时的顺序是$2 \; 3 \; 4 \; 5 \; 1$。
两次计算中重复计算的量有$[2,3],[3,4],[4,5],[2,4],[3,5],[2,5]$(方括号中的数字代表编号)
我们可以考虑将数组扩大一倍,令$a[n+1]=a[1],a[n+2]=a[2]…a[n+n]=a[n]$.(最后一个没用,因为是循环)
这样一i为起点的答案就是$d[i][i+n-1]$,扫一遍取最大就行了。
这样就将复杂度降为$O(n^3)$了。
The Code Of My Program AC代码
1 | /********************* |
矩阵取数游戏
题目描述 Description
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的$ n * m $ 的矩阵,矩阵中的每个元素$a_{ij}$均为非负整数。游戏规则如下:
- 每次取数时须从每行各取走一个元素,共$n$个。$m$次后取完矩阵所有元素;
- 每次取走的各个元素只能是该元素所在行的行首或行尾;
- 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分= 被取走的元素值$ * 2^i$,其中$i$表示第$i$次取数(从$1$开始编号);
- 游戏结束总得分为$m$次取数得分之和。
帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。
输入描述 Input Description
第$1$行为两个用空格隔开的整数$n$和$m$。
第$ 2 $ ~ $ n+1 $ 行为$ n * m $矩阵,其中每行有m个用单个空格隔开的非负整数。
输出描述 Output Description
输出 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。
样例输入 Sample Input
2 3
1 2 3
3 4 2
样例输出 Sample Output
82
数据范围及提示 Data Size & Hint
样例解释
第 1 次:第$1$行取行首元素,第$2$行取行尾元素,本次得分为$1 * 2^1+2 * 2^1=6$
第 2 次:两行均取行首元素,本次得分为$2 * 2^2 + 3 * 2^2 = 20$
第 3 次:得分为$3 * 2^3+4 * 2^3=56$。总得分为$6+20+56=82$
【限制】
$ 60 % $ 的数据满足:$1 \leq n, m \leq 30$, 答案不超过$10^{16}$
$100 % $ 的数据满足:$1 \leq n, m \leq 80, 0 \leq aij \leq 1000$
Consideration 想法
首先读题后,我们发现行与行之间相互独立没有干扰,这样我们就可以读一行处理一行,每一行都是一个单独的问题,相当于给了n组数据,求出答案的和。
这样我们把空间从n²降到了n。
接下来开始考虑思路。不难发现,取走一部分数字后,剩下的数字总是形成一个区间。由于取走的数的个数已知,剩下的数字按顺序的权值也就知道了,由此得出,这是一个区间DP,和石子合并类似。它满足最优子结构,也满足无后效性。
用f[i][j]表示区间[i, j]的最优解,有两种解法
f[i][j] = max(a[i] + 2 * f[i+1][j], a[j] + 2 * f[i][j-1]);//直接计算数的权值
f[i][j] = max(a[i]*2^(m-j+i) + f[i+1][j], a[j]*2^(m-j+i) + f[i][j-1])//每次翻倍
第一种,就是先做一个二的幂次方表,直接计算,很好理解。
第二种,也是更加方便的一种,只需要每次将小区间乘二即可,应用了乘法分配律的原理。进行完整个区间后,区间长度小乘的次数就多,最后的效果也是二的幂次方。应该也不难理解吧
这里最恶心的是要高精度…..所以我wa了
The Code Of My Program WA代码
1 | //codevs1166 矩阵取数游戏 区间DP+高精 |