传纸条
http://www.rqnoj.cn/Problem_400.html
【问题分析】
这个题目要求我们在一个给定的矩阵中选择不相交的两条路径(首尾除外,而且必须相交),使得路径上的所有数和最大。
【算法描述】
这类题目有两种做法,一种是动态规划,一种是最小费流。由于最小费流实现比较复杂,没有什么实际意义,所以不再赘述。
由于两条路径的长度相等,可以用f[k][p][q][x][y]表示在前k的长度中,两条路径的结束点分别在(p,q)、(x,y)的最大权值。显然,这个状态是满足无后效性的,因为路径不可以掉头。而且同时也满足最优性原理,因为当前这个状态必然由若干个子状态演变而来。
可以写出下面的状态转移方程:
f[k][p][q][x][y]=max{f[k-1][p’][q’][x’][y’]}+val[p][q]+val[x][y]
这里,val[i][j]表示第i行第j列的数字大小,要求(p,q)与(p’,q’)相邻,(x,y)与(x’,y’)相邻,而且(p’,q’)≠(x’,y’)。
状态初始化为f[1][1][1][1][1]=val[1][1]。
分析一下算法的复杂度,时间复杂度为O(n3),空间复杂度为O(n5)。由于n≤50,使得使用的空间最大可以达到1.2GB,显然是不可以接受的,我们要对其进行优化。
一个事实是这样的:如果知道了长度k和横坐标x,那么可以计算出纵坐标y。所以状态可以压缩为f[k][p][x],这样在空间上就可以接受了。但是记录步数需要2n+1的维度,而
2
NOIP2008 提高组解题报告 2009-1-4
如果知道了坐标,就可以算出步数,所以状态可以更改为f[p][q][x],这样比刚才优化过的状态少使用了一半的空间。至此,空间上仅仅使用了488KB,可谓优化效果明显。
【题目小结】
这道题目是2001分区联赛的原题目,在曹老师的《数学建模》讲义中也出现过。就难度而言并不算难题,但是很多人因为内存的问题而丢掉了一道题目的分数。要求我们在审题的时候要注意每一个细节。
dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2],dp[x1-1][y1][x2][y2-1],
dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1])+map[x1][y1];
if(x1!=x2 || y1!=y2)
dp[x1][y1][x2][y2] += map[x2][y2];
AC代码:
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 52
using namespace std;
int dp[MAXN][MAXN][MAXN][MAXN],map[MAXN][MAXN];
int Max(int a,int b){
return a>b?a:b;
}
int max(int a,int b,int c,int d){
int t1=Max(a,b);
int t2=Max(c,d);
return Max(t1,t2);
}
int main()
{
freopen("input.txt","r",stdin);
int m,n,i,j,x1,y1,x2,y2;
while(scanf("%d %d",&m,&n)!=EOF){
for(i=1; i<=m; ++i){
for(j=1; j<=n; ++j)
scanf("%d",&map[i][j]);
}
memset(dp,0,sizeof(dp));
for(x1=1; x1<=m; ++x1){
for(y1=1; y1<=n; ++y1){
for(x2=1; x2<=m; ++x2){
for(y2=1; y2<=n; ++y2){
dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2],dp[x1-1][y1][x2][y2-1],
dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1])+map[x1][y1];
if(x1!=x2 || y1!=y2)
dp[x1][y1][x2][y2] += map[x2][y2];
}
}
}
}
printf("%d\n",dp[m][n][m][n]);
}
return 0;
}
开三维数组的方法:
由于只能走右或下,所以坐标满足x+y=k。这样就能降低维数为3维,方程(核心代码):
// 核心代码
dp[k][x1][x2]=max(dp[k-1][x1][x2],dp[k-1][x1-1][x2-1],
dp[k-1][x1-1][x2],dp[k-1][x1][x2-1])+map[x1][y1];
if(x1!=x2 || y1!=y2)
dp[k][x1][x2] += map[x2][y2];
AC代码:
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 52
using namespace std;
int dp[MAXN*2+1][MAXN][MAXN],map[MAXN][MAXN];
int Max(int a,int b){
return a>b?a:b;
}
int max(int a,int b,int c,int d){
int t1=Max(a,b);
int t2=Max(c,d);
return Max(t1,t2);
}
int main()
{
// freopen("input.txt","r",stdin);
int m,n,i,j,k,x1,y1,x2,y2;
while(scanf("%d %d",&m,&n)!=EOF){
for(i=1; i<=m; ++i){
for(j=1; j<=n; ++j)
scanf("%d",&map[i][j]);
}
memset(dp,0,sizeof(dp));
for(k=1; k<=n+m-1; ++k){
for(x1=1; x1<=k; ++x1){
for(x2=1; x2<=k; ++x2){
y1=k+1-x1;
y2=k+1-x2;
dp[k][x1][x2]=max(dp[k-1][x1][x2],dp[k-1][x1-1][x2-1],
dp[k-1][x1-1][x2],dp[k-1][x1][x2-1])+map[x1][y1];
if(x1!=x2 || y1!=y2)
dp[k][x1][x2] += map[x2][y2];
}
}
}
printf("%d\n",dp[m+n-1][m-1][m]);
}
return 0;
}
MatrixHDU 2686http://acm.hdu.edu.cn/showproblem.php?pid=2686
和传纸条类似
四维数组方法:
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 52
using namespace std;
int dp[MAXN][MAXN][MAXN][MAXN],map[MAXN][MAXN];
int Max(int a,int b){
return a>b?a:b;
}
int max(int a,int b,int c,int d){
int t1=Max(a,b);
int t2=Max(c,d);
return Max(t1,t2);
}
int main()
{
// freopen("input.txt","r",stdin);
int n,i,j,x1,y1,x2,y2;
while(scanf("%d",&n)==1){
for(i=1; i<=n; ++i){
for(j=1; j<=n; ++j)
scanf("%d",&map[i][j]);
}
memset(dp,0,sizeof(dp));
for(x1=1; x1<=n; ++x1){
for(y1=1; y1<=n; ++y1){
for(x2=1; x2<=n; ++x2){
for(y2=1; y2<=n; ++y2){
dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2],dp[x1-1][y1][x2][y2-1],
dp[x1][y1-1][x2-1][y2],dp[x1][y1-1][x2][y2-1])+map[x1][y1];
if(x1!=x2 || y1!=y2)
dp[x1][y1][x2][y2] += map[x2][y2];
}
}
}
}
printf("%d\n",dp[n][n][n][n]);
}
return 0;
}
2.三维数组方法:
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 32
using namespace std;
int dp[MAXN*2+1][MAXN][MAXN], map[MAXN][MAXN];
int max(int a,int b,int c,int d){
int t1=a>b?a:b;
int t2=c>d?c:d;
return t1>t2?t1:t2;
}
int main()
{
int n,i,j,k,x1,x2,y1,y2;
while(scanf("%d",&n)!=EOF){
for(i=1; i<=n; ++i){
for(j=1; j<=n; ++j)
scanf("%d",&map[i][j]);
}
memset(dp,0,sizeof(dp));
for(k=1; k<=2*n-1; ++k){
for(x1=1; x1<=k; ++x1){
for(x2=1; x2<=k; ++x2){
y1 = k+1-x1;
y2 = k+1-x2;
dp[k][x1][x2] = max(dp[k-1][x1][x2],dp[k-1][x1-1][x2-1],
dp[k-1][x1-1][x2],dp[k-1][x1][x2-1])+map[x1][y1];
if(x1!=x2 || y1!=y2)
dp[k][x1][x2] += map[x2][y2];
}
}
}
printf("%d\n",dp[k-1][n-1][n]);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
测试输入关于“测试输入”的帮助 期待的输出关于“期待的输出”的帮助 时间限制关于“时间限制”的帮助 内存限制关于“内存限制”的帮助 额外进程关于“{$a} 个额外进程”的帮助 测试用例 1 以文本方式显示 4↵ 0:...
从 1994 年 Mar 的论文开始,已经出现了很多算法。可以分成在线和离线两大类。它们都不够实用,具体体现在……(略)。 为了克服现有算法的缺点,本文首先提出并证明了“最优低功耗调度定理”,还证明了任何在线算法...
pushd, 快速的多协议移动和网络推送通知服务 通用移动推送守护进程这就是一个可以向移动本地应用程序发送服务器端通知的服务器,你可以从一个入口点向任何支持的移动平台,网络应用程序或者HTTP服务器发送推送通知。...
4.1 一对多广播以及多对一归约 4.1.1 环或线性阵列 4.1.2 格网 4.1.3 超立方体 4.1.4 平衡二叉树 4.1.5 算法细节 4.1.6 成本分析 4.2 多对多广播和归约 4.2.1 线性阵列和环 4.2.2 格网 4.2.3 超立方体 ...
(bluetooth.stack)(btstack),可以运行在STM32,Linux.,包含HCI,L2CAP,SDP,RFCOMM,HFP,SPP,A2DP,AVRCP,AVDTP,AVCTP,OBEX,PBAP等协议,后续会继续维护 运维(Operations & Maintenance,简称O&M)是IT行业中至关重要...
hyLISP hyLISP是在FreeBSD上运行一个... 管理程序允许多个控制平面进程轻松地与数据平面交互。 目前,消息在每个 EID 的基础上在数据和控制平面之间进行多路复用和多路分离; 然而,虚拟机管理程序可以(并且有望)扩
怎么刷leetcode 访谈主题 注意:- 如果您觉得这篇文章有用,请点赞!! 如果我忘记添加任何主题,请在评论部分告诉我 感谢读者对本文的出色回应。...进程(属性、状态、生命周期、PCB)与线程。 调度算法 多道程
|--Manager之ActivityManager进程管理 |--Manager之LocationManager |--Manager之PackageManager |--Menu之不同模式下显示不同菜单 |--openGL-ES上绘制文字 |--openGL-ES纹理贴图 |--openGL-ES获取帧率 |--openGL-ES...
该方案针对光纤到户特点,包含蝶形光缆,以及结构微型化的光缆,这些光缆既具有良好光学特性又便于施工,全面提速了光纤入户的进程。能快速成端的快速连接器,提供ONU接口的光纤信息面板,起到光分路器下沉的DP盒等...
7.4.4 基于a2dp的蓝牙音频设备hal实现 /402 7.4.5 模拟器上的audio hal实现 /403 7.5 android ril实现 /404 7.5.1 android ril构架 /404 7.5.2 radiooptiongs实现 /407 7.5.3 libril库实现 /409 7.5.4 reference-ril...
10.9 cp_dpis函数 10.10 cp_reass函数 10.11 小结 第11章 /CP实现:CP输入 11.1 概述 11.2 预处理 11.3 首部预测 11.4 被动打开的启动 11.5 主动打开的启动 11.6 PAWS:防止序号重复 11.7 ACK处理 11.8 完成被动打开...
7.4.4 基于a2dp的蓝牙音频设备hal实现 /402 7.4.5 模拟器上的audio hal实现 /403 7.5 android ril实现 /404 7.5.1 android ril构架 /404 7.5.2 radiooptiongs实现 /407 7.5.3 libril库实现 /409 7.5.4 ...