- 题目描述:
-
现在有一个8*8的棋盘,上面放着64个价值不等的礼物,每个小的棋盘上面放置一个礼物(礼物的价值大于0小于1000),一个人的初始位置在棋盘的左上角,每次他只能向下或向右移动一步,并拿走对应棋盘上的礼物,结束位置在棋盘的右下角,请设计一个算法使其能够获得最大价值的礼物。
- 输入:
-
输入包含多个测试用例,每个测试用例共有8行8列,第i行的第j列的数字代表了该处棋盘上的礼物的价值,每两个数之间用空格隔开。
- 输出:
-
对于每组测试用例,请输出你能够获得最大价值的礼物。
- 样例输入:
-
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
样例输出:
194
思路:
dp[0][0]=map[0][0];
把列为0行为1到7的所有的最优的dp[i][0]求出;dp[i][0]=dp[i-1][0]+map[i][j];
把行为0列为1到7的所有的最优的dp[0][j]求出; dp[0][j]=dp[0][j-1]+map[i][j];
然后再由
for(i=1;i<8;i++)
for(j=1;j<8;j++)
dp[i][j]=max{dp[i-1][j],dp[i][j-1]};
其中dp[i-1][j]表示左边走过来的,dp[i][j-1]表示上边走下来的
AC code
#include<stdio.h> #include<string.h> int map[8][8]; int dp[8][8]; int Max(int a,int b) { return a>b?a:b; } int main() { int i,j; while(scanf("%d",&map[0][0])!=-1) { for(i=0;i<8;i++) for(j=0;j<8;j++) if(j!=0||i!=0) scanf("%d",&map[i][j]); memset(dp,0,sizeof(dp)); dp[0][0]=map[0][0]; for(i=1;i<8;i++) dp[i][0]=dp[i-1][0]+map[i][0]; for(j=1;j<8;j++) dp[0][j]=dp[0][j-1]+map[0][j]; for(i=1;i<8;i++) for(j=1;j<8;j++) dp[i][j]=Max(dp[i-1][j],dp[i][j-1])+map[i][j]; printf("%d\n",dp[7][7]); } return 0; }