频道栏目
首页 > 考试 > 其他 > 正文

zzulioj 1875 蛤玮的财宝 ( “玲珑杯”郑州轻工业学院第八届ACM程序设计大赛暨河南高校邀请赛-正式赛 双线dp)

2016-04-30 09:11:40         来源:苏苏爱自由  
收藏   我要投稿

 

1875: 蛤玮的财宝

Description

蛤玮和他的妹子出海游玩,不小心遭遇了海难,他们醒来之后发现自己到了一座金银岛.岛主非常好心的告诉他们在岛的另一边有船可以送他们回家.

这座岛可以看成n*m的矩阵,蛤玮他们在位置(1,1),而船在位置(n,m).蛤玮发现金银岛遍地都是金子,每个格子里有价值a[i,j]的金子,他和妹子打算在回去的路上带一些走.如果他们路过了位置(i,j),就可以假装系鞋带捡走地上的金子.为了不引起怀疑,他们在走的时候只能往接近码头的方向走,即如果蛤玮现在在(i,j),他只能移动到(i+1,j)或者(i,j+1).为了能拿走更多的金子,蛤玮和妹子决定装作互相不认识,这样他们就可以分开走,从而拿到更多的金子.

蛤玮和他妹子想知道他们最多能拿走多少金子.

注意如果蛤玮和他妹子经过了相同的地方,只能得到一次金子,因为地上的捡完就没有了.

 

Input

 

T(1<=T<=10),表示数据组数.

每组数据第一行n,m(1<=n,m<=100),接下来n行,每行m个数,第i行第j列的值a[i,j](1<=a[i,j]<=1000)表示位置(i,j)的金子的价值.

 

Output

 

每组数据输出一行,蛤玮和他妹子能拿到的金子总价的最大值.

 

Sample Input

12 22 11 2

Sample Output

6

HINT

 

Source

 

 

不能用四维的动态规划方程 会超内存。。

通过步数相等 转换为3维的 前面做过 我就不多说了 不懂得看看这道相似的题

和这篇文章类似

 



  [cpp] view plain copy print?

在CODE上查看代码片
派生到我的代码片

 

  #include

  #include

  #include

  using namespace std;

  int dp[210][105][105];

  int main()

  {

  int ncase;

  int map[105][105];

  scanf("%d",&ncase);

  while(ncase--)

  {

  int n,m;

  memset(map,0,sizeof(map));

  memset(dp,0,sizeof(dp));

  scanf("%d %d",&n,&m);

  for(int i=1;i<=n;i++)

  for(int j=1;j<=m;j++)

  scanf("%d",&map[i][j]);

  int step=n+m-2;

  for(int i=1;i<=n;i++)

  {

  for(int j=1;j<=n;j++)

  {

  for(int k=1;k

  {

  if(i==j)

  break;

  if(k+2>=i&&k+2>=j)

  dp[k][i][j]=max(max(dp[k-1][i][j],dp[k-1][i][j-1]),

  max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]))+map[i][k+2-i]+map[j][k+2-j];

  }

  }

  }

  int result=max(dp[step-1][n-1][n],dp[step-1][n][n-1])+map[n][m]+map[1][1];

  printf("%d\n",result);

  }

  }

上一篇:[剑指offer] 浮点数的整数次方
下一篇:链表倒数第n个节点
相关文章
图文推荐
文章
推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站