339
九度題目1529：棋盤尋寶
題目1529：棋盤尋寶
時間限製：1 秒
內存限製：128 兆
特殊判題：否
提交：682
解決：306
題目描述：
現在有一個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
來源：
微策略2012年校園招聘筆試題
經典的dp：
#include<stdio.h>
#include<string.h>
int a[10][10],dp[10][10];
int max(int n,int m)
{return n>m?n:m;}
int main()
{
int i,j,n,m;
while(scanf("%d",&a[1][1])!=EOF)//防止超時（用while(1)一定會超時，以後慎用！！）
{
memset(dp,0,sizeof(dp));
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
{
if(i==1&&j==1)
continue;
scanf("%d",&a[i][j]);
}
dp[1][1]=a[1][1];
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
{
if(i==1&&j==1)
continue;
if(i==1)
{
dp[i][j]=dp[i][j-1]+a[i][j];
continue;
}
if(j==1)
{
dp[i][j]=dp[i-1][j]+a[i][j];
continue;
}
dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]);
}
printf("%d\n",dp[8][8]);
memset(a,0,sizeof(a));
}
return 0;
}
最後更新：2017-04-03 12:56:25