进入OJ
Description
现在有一个8*8的棋盘,上面放着64个不同价值的礼物,每个小的棋盘上面放置一个礼物(礼物的价值大于0小于100),一个人初始位置在棋盘的左上角,每次他只能向下或向右移动一步,并拿走对应棋盘上的礼物,结束位置在棋盘的右下角。从棋盘的左上角移动到右下角的时候的,每次他只能向下或向右移动一步,并拿走对应棋盘上的礼物,但是拿到的所有的礼物的价值之和不大于一个限定值limit,请设计一个算法请实现,使其能够获得不超过限制值limit的最大价值的礼物。
Input
输入包含多个测试用例,每个测试用例共有9行,第一行是一个限制值limit<=1000,下面还有8行8列,第i行的第j列的数字代表了该处棋盘上的礼物的价值,每两个数之间用空格隔开。
Output
对于每组测试用例,请输出你能够获得不超过限制值limit的最大价值的礼物。若没有符合条件的线路则输出-1。
Sample Input
90
4 2 5 1 3 8 9 7
4 5 2 3 7 1 8 6
7 2 1 8 5 9 3 6
2 8 9 5 6 3 1 7
1 2 4 5 3 7 9 6
3 5 7 8 9 6 2 4
10 8 1 4 7 5 3 9
7 4 6 2 1 3 9 8
4 2 5 1 3 8 9 7
4 5 2 3 7 1 8 6
7 2 1 8 5 9 3 6
2 8 9 5 6 3 1 7
1 2 4 5 3 7 9 6
3 5 7 8 9 6 2 4
10 8 1 4 7 5 3 9
7 4 6 2 1 3 9 8
Sample Output
90
Hint
动态规划
Source
微策略2012年校园招聘笔试题
Code
方法一:
#include <stdio.h> int map[8][8], i, j, ans, limit; void f(int x, int y, int sum) { sum += map[x][y]; if (sum > limit) return; if (x == 7 && y == 7 && sum > ans) ans = sum; if (x < 7) f(x + 1, y, sum); if (y < 7) f(x, y + 1, sum); } int main() { while(~scanf("%d",&limit)) { ans = 0; for(i=0; i<8; i++) { for(j=0; j<8; j++) { scanf("%d",&map[i][j]); } } f(0,0,0); if(ans > 0) printf("%d\n",ans); else puts("-1"); } return 0; }
方法二:
#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,int sum,int limit) { sum += x[m][n]; int re; if(sum > limit || x[m][n] > limit) return -1; if(m == 0 && n==0) return x[0][0]; if(m-1<0) re = fun(m,n-1,sum,limit); else if(n-1<0) re = fun(m-1,n,sum,limit); else re = MAX(fun(m-1,n,sum,limit),fun(m,n-1,sum,limit)); if(re>0) return re+x[m][n]; else return -1; } int main() { int n; while(scanf("%d",&n)!=EOF) { for(int o=0;o<8;o++) for(int i=0;i<8;i++) scanf("%d",&x[o][i]); ; printf("%d\n",fun(7,7,0,n)); } }
高智商。