题目描述
Shekhu教授有一个N行M列的矩阵,其中行从上到下按0到N-1编号,列从左到右按0到M-1编号。
矩阵中的每个单元格包含一个正整数。
他想通过水平和垂直切割将这个矩阵切割成N * M个子矩阵(每个子矩阵大小为1 * 1)。
注意,只能在两行或两列之间的边界上进行切割。
Shekhu教授找来了他最好的学生Akki来完成这项工作并提出一个有趣的建议。
每次Akki在某个子矩阵中进行切割时,在他进行切割之前,他都会获得等于该子矩阵包含的最小数值的硬币数量。
请注意,每次切割时,子矩阵的总数都会增加。
此外,任意两个不同子矩阵的切割是独立的,同样,Akki对不同子矩阵的每次切割都是独立的。
现在,Akki有多种方式可以进行切割。
你可以通过最大化他可以获得的硬币总数来帮助他吗?
样例
3
2 2
1 2
3 4
2 3
1 2 1
2 3 2
1 2
1 2
算法
观察到数据范围中矩阵的行和列均不超过40,设计状态dp1(x1,y1,x2,y2),表示对左上角为(x1,y1),右下角为(x2,y2)的矩阵进行切割,最终得到的最大分数。状态转移的过程即枚举对左上角为(x1,y1),右下角为(x2,y2)的矩阵进行一次横切还是一次竖切,以及切割线位置。
若沿x=x3进行一次竖切
dp1(x1,y1,x2,y2)=max(dp1(x1,y1,x2,y2),dp1(x1,y1,x3,y2)+dp1(x3+1,y1,x2,y2)+coin(x1,y1,x2,y2))
若沿y=y3进行一次横切
dp1(x1,y1,x2,y2)=max(dp1(x1,y1,x2,y2),dp1(x1,y1,x2,y3)+dp1(x1,y3+1,x2,y2)+coin(x1,y1,x2,y2))
根据状态的转移方程,采取记忆化搜索更易实现,作者对记忆化搜索不熟悉,又看到很多题解都采用了记忆化搜索,于是决定采用传统的递推方法来解决本题,相应地,状态定义也需要作出修改。
首先需要明确的是,动态规划问题的三要素包括状态,阶段,决策。对于难以描述阶段变化的状态,我们采用记忆化搜索解决问题;换言之,若针对定义的状态可以轻易地进行阶段的变更,就能采用递推方法进行求解。
先考虑问题的一种简化形式,即矩阵为1*M的情况,问题转化为区间dp问题,设计状态dp2(l,r),则枚举端点k,转移方程为
dp2(l,r)=max(dp2(l,r),dp2(l,k)+dp2(k+1,r)+coin(l,r))
与经典的石子合并问题十分相似。通过发散思考,可以发现本题实质上是一个二维区间dp。联系到经典的石子合并问题中的阶段扩展,其思想是将阶段————即区间的长度由1逐渐增加至石子总堆数。具体实现方法是在三重循环中,先枚举区间长度len,在枚举区间左端点l,然后就可以计算出右端点r=l+len-1,注意,这里的r是计算得到的,而不是枚举得到的————这样处理的优点在于显式地给出了阶段z扩展的过程,使得问题能够通过递推实现。
模仿石子合并问题的思考过程,我们需要先枚举子矩阵在纵向上的长度_i_,在纵向上的起始坐标u,在横向上的长度j,在横向上的起始坐标v。设计状态dp3(i,j,u,v)表示左上角为(u,v)的i*j矩阵的最大得分,转移方程为
dp3[i][j][u][v]=max(dp3[i][j][u][v],dp3[x][j][u][v]+dp3[i-x-1][j][u+x+1][v]+coin[i][j][u][v])
dp3[i][j][u][v]=max(dp3[i][j][u][v],dp3[i][y][u][v]+dp3[i][j-y-1][u][v+y+1]+coin[i][j][u][v])
具体的代码段为
for(i=0;i<=N-1;i++){
for(j=0;j<=M-1;j++){
if(i==0&&j==0) continue;
for(u=1;u<=N-i;u++){
for(v=1;v<=M-j;v++){
if(i){
for(x=0;x<i;x++) dp[i][j][u][v]=max(dp[i][j][u][v],dp[x][j][u][v]+dp[i-x-1][j][u+x+1][v]+coin[i][j][u][v]);
}
if(j){
for(y=0;y<j;y++) dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][y][u][v]+dp[i][j-y-1][u][v+y+1]+coin[i][j][u][v]);
}
}
}
}
}
在实现过程中,作者走过弯路,在显式地对阶段进行扩展后,仍然采用了状态dp1,即枚举左上角(i,j)和右下角(i+x,j+y),具体的代码段为:
for(x=0;x<=N-1;x++){
for(y=0;y<=M-1;y++){
if(x==0&&y==0) continue;
for(i=1;i<=N-x;i++){
for(j=1;j<=M-y;j++){
if(x){
for(u=i+1;u<=i+x;u++) dp[i][j][i+x][j+y]=max(dp[i][j][i+x][j+y],dp[i][j][u-1][j+y]+dp[u][j][i+x][j+y]+coin[i][j][i+x][j+y]);
}
if(y){
for(v=j+1;v<=j+y;v++) dp[i][j][i+x][j+y]=max(dp[i][j][i+x][j+y],dp[i][j][i+x][v-1]+dp[i][v][i+x][j+y]+coin[i][j][i+x][j+y]);
}
}
}
}
}
这两段代码的时间复杂度相同,但由于状态定义上的区别,运行时间有着很大的差异,后者会使程序超时。作者也解释不太清楚,应该是cache命中率的区别导致两段程序存在常数倍运算时差,考研的同学可以看看王道408中机组的cache部分。
参考文献
算法竞赛进阶指南 区间dp
C++ 代码
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
#include<ctime>
using namespace std;
int T,N,M,cnt,i,j,k,u,v,x,y;
int matrix[50][50],coin[50][50][50][50],dp[50][50][50][50];
double total;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++){
for(j=1;j<=M;j++) scanf("%d",&matrix[i][j]);
}
double st=clock();
memset(dp,0,sizeof(dp));
for(i=1;i<=N;i++){
for(j=1;j<=M;j++) coin[0][0][i][j]=matrix[i][j];
}
for(i=0;i<=N-1;i++){
for(j=0;j<=M-1;j++){
if(i==0&&j==0) continue;
for(u=1;u<=N-i;u++){
for(v=1;v<=M-j;v++){
int temp=matrix[u+i][v+j];
if(i) temp=min(temp,coin[i-1][j][u][v]);
if(j) temp=min(temp,coin[i][j-1][u][v]);
coin[i][j][u][v]=temp;
}
}
}
}
for(i=0;i<=N-1;i++){
for(j=0;j<=M-1;j++){
if(i==0&&j==0) continue;
for(u=1;u<=N-i;u++){
for(v=1;v<=M-j;v++){
if(i){
for(x=0;x<i;x++) dp[i][j][u][v]=max(dp[i][j][u][v],dp[x][j][u][v]+dp[i-x-1][j][u+x+1][v]+coin[i][j][u][v]);
}
if(j){
for(y=0;y<j;y++) dp[i][j][u][v]=max(dp[i][j][u][v],dp[i][y][u][v]+dp[i][j-y-1][u][v+y+1]+coin[i][j][u][v]);
}
}
}
}
}
cnt++;
printf("Case #%d: %d\n",cnt,dp[N-1][M-1][1][1]);
double ed=clock();
// total=total+ed-st;
// if(total>2000000){
// printf("%.0lf %d\n",total,cnt);
// break;
// }
}
}