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)
加油。
最新文章
- samba共享目录
- SVG图案填充-Pattern
- [转] 经典SQL练习题
- linux中oops信息的调试及栈回溯【转】
- 显示全部select change 异常
- IntelliLock
- js 动态时钟
- 在PHP5.3以上版本运行ecshop和ecmall出现的问题及解决方案
- iOS开发中xib和Storyboard中需要注意的事项
- 通用的contain函数
- 序列化与transient
- web 11
- 内置委托func
- ajax之async属性
- python中的str和repr函数的区别
- 推荐一篇文章 《为什么C语言不会过时?》
- 学习笔记之Nearest-Neighbour Searching with PostGIS
- window搭建Tomcat服务
- Benefit UVA - 11889(已知LCM和其中一个数,求另一个数)
- LOG4J spring与mybatis整合