提高矩阵运算效率（P1005 [NOIP2007 提高组] 矩阵取数游戏）

题目传送门

前言

今天依旧是不写高精的一天呢！（是的  
  
  
  
  
  
  
 ，这位作者又只拿了开 \(LL\) 的 \(\color{yellow}{60}\) 分）

思路描述

看到数据 \(n,m \le 80(30)\) 就知道数组可以任性开 
  
  
  
  
  
  
 ，心理有个底后


 


 


 


 


 


 


 
，再来看题目              。

状态描述

首先肯定要来一个 \(dp_{i,j}\) 来表示第 \(i\) 次时取第 \(j\) 行的数 
 
  
 
  
 
  
 
  
 
  
 
  
 
  。

对于每一次放置 
 
 
 
 
 
 
，我们要考虑到的是之前每一次都取到什么,也就是现在的头和尾分别是哪两个数













。

想明白这一点  
   
   
   
   
   
   
  ，就可以描述状态了
  
  
  
  
  
  
  
。

\(dp_{i,j,k,t}\) 表示第 \(i\) 次时取第 \(j\) 行的数

 

 

 

 

 

 

 
，对于第 \(j\) 行
 

 

 

 

 

 

 
，它的行首被取了 \(k\) 个数               ，他的行尾被取了 \(t\) 个数 
  
  
  
  
  
  
 。

由于 $t = i - k $ 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
，当 \(i













，k\) 确定时                      ，\(t\) 也一定唯一
 
 
 
 
 
 
 
 
 
 
 
 
 
 
，因此可以省略 


 


 


 


 


 


 


 。

状态转移方程

描述出状态了




















，状态转移方程还会远吗？

显然有

\(dp_{i,j,k} = \max(dp_{i-1,j,k-1}+val（i,j,k）,dp_{i-1,j,k}+val(i,j,m-(i-k)+1))\)
 
 
 
 
 
 
 
。

\(val(x,y,z)\) 表示第 \(x\) 次时取位于第 \(y\) 行第 \(z\) 列的数所能获得的得分  
   
   
   
   
   
   
 。

\(\max\) 中的两者分别对应了第 \(i\) 次时               ，在第 \(j\) 行取队首 \(or\) 队尾的情况 

 

 

 

 

 

 

 。

code

点击查看代码 #include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; int n,m; ll a[85][85],dp[85][85][85]; int bas[31]; int main(){ scanf("%d%d",&n,&m); bas[0]=1; for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ dp[i][j][i]=dp[i-1][j][i-1]+a[j][i]*bas[i],dp[i][j][0]=dp[i-1][j][0]+a[j][m-i+1]*bas[i];//这两种情况比较特殊
 
  
 
  
 
  
 
  
 
  
 
  
 
  
，所以单独列

 

 

 

 

 

 

 
。 for(int k=1;k<i;k++){ dp[i][j][k]=max(dp[i-1][j][k-1]+a[j][k]*bas[i],dp[i-1][j][k]+a[j][m-(i-k)+1]*bas[i]); } } } ll ans=0; for(int i=1;i<=n;i++){ ll max_num=0; for(int j=0;j<=m;j++) max_num=max(max_num,dp[m][i][j]); ans+=max_num; } cout<<ans<<endl; return 0; }

ps：经过作者后续习惯性翻翻题解（发现原来区间DP也可以做）













，以及打输出时的共同启发  
  
  
  
  
  
  
 ，发现实际上我们只需要分别枚举对于每一行是的最优解 
  
  
  
  
  
  
 ，加起来就可以了              。因此状态中表示行的那一维可以省略 
 

 
 

 
 

 
 

 
 

 
 

 
 

 。然后就有了以下代码














。

点击查看代码 #include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; int n,m; ll a[85][85],dp[85][85]; int bas[31]; int main(){ scanf("%d%d",&n,&m); bas[0]=1; for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); ll ans=0,max_num; for(int j=1;j<=n;j++){ for(int i=1;i<=m;i++){ dp[i][i]=dp[i-1][i-1]+a[j][i]*bas[i],dp[i][0]=dp[i-1][0]+a[j][m-i+1]*bas[i]; for(int k=1;k<i;k++){ dp[i][k]=max(dp[i-1][k-1]+a[j][k]*bas[i],dp[i-1][k]+a[j][m-(i-k)+1]*bas[i]); } } max_num=0; for(int i=0;i<=m;i++) max_num=max(max_num,dp[m][i]); ans+=max_num; } cout<<ans<<endl; return 0; }

事实上没太大区别


 


 


 


 


 


 


 
，毕竟它的数据范围可以让我任性开（首尾呼应.jpg(确信)）                     。

summary

对于省略维数有了更深刻的理解 
 
 
 
 
 
 
 
 
 
 
 
 
 
 。

可以用其他维度表示的可以省略





















。

可以通过分开解决时不需要整体来定义              。

\(dp\)百道第六题 
 
  
 
  
 
  
 
  
 
  
 
  
 
  。（照这个进度可能得一年后在看看有没有百道的希望了QWQ）

加油













。