i3geek.com
闫庚哲的个人博客

1014 棋盘寻宝【微策略2012年校园招聘笔试题】

进入OJ

Description

现在有一个8*8的棋盘,上面放着64个价值不等的礼物,每个小的棋盘上面放置一个礼物(礼物的价值大于0小于1000),一个人的初始位置在棋盘的左上角,每次他只能向下或向右移动一步,并拿走对应棋盘上的礼物,结束位置在棋盘的右下角,请设计一个算法使其能够获得最大价值的礼物。

Input

输入包含多个测试用例,每个测试用例共有8行8列,第i行的第j列的数字代表了该处棋盘上的礼物的价值,每两个数之间用空格隔开。

Output

对于每组测试用例,请输出你能够获得最大价值的礼物。http://oj.i3geek.com/problemset.php

Sample Input

2 8 15 1 10 5 19 19
3 5 6 6 2 8 2 12
16 3 8 17 12 5 3 14
13 3 2 17 19 16 8 7
12 19 10 13 8 20 16 15
4 12 3 14 14 5 2 12
14 9 8 5 3 18 18 20
4 2 10 19 17 16 11 3

Sample Output

194

Hint

动态规划

Source

微策略2012年校园招聘笔试题

Code

方法一:


#include <iostream>
#include<stdio.h>
#include <string.h>
using namespace std;
int x[8][8];
int MAX(int a,int b)
{
    return a>b?a:b;
}
int fun(int m,int n)
{

    if(m == 0 && n==0)
        return x[0][0];
    if(m-1<0)
        return fun(m,n-1)+x[m][n];
    if(n-1<0)
        return fun(m-1,n)+x[m][n];
    return MAX(fun(m-1,n),fun(m,n-1))+x[m][n];
}
int main()
{
    while(scanf("%d",&x[0][0])!=EOF)
    {
        for(int i=1;i<8;i++)
            scanf("%d",&x[0][i]);
        for(int o=1;o<8;o++)
            for(int i=0;i<8;i++)
                scanf("%d",&x[o][i]);
        printf("%d\n",fun(7,7));
    }
}

方法二:


#include <stdio.h>
int map[8][8], i, j, ans;
int main() {
	while(~scanf("%d",&map[0][0])) {
		for(j=1; j<8; j++) {
			scanf("%d",&map[0][j]);
			map[0][j] += map[0][j-1];
		}
		for(i=1; i<8; i++) {
			scanf("%d",&map[i][0]);
			map[i][0] += map[i-1][0];
			for(j=1; j<8; j++) {
				scanf("%d",&map[i][j]);
				map[i][j] += (map[i][j-1] > map[i-1][j] ? map[i][j-1]:map[i-1][j]);
			}
		}
		printf("%d\n",map[7][7]);
	}
	return 0;
}

 

赞(0)
未经允许不得转载:爱上极客 » 1014 棋盘寻宝【微策略2012年校园招聘笔试题】
分享到: 更多 (0)

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    怎么url还有汉字啊,对SEO可很不好好啊

    知道91博客5年前 (2014-11-12)回复