题目4：棋盘寻宝扩展
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：59
解决：32
- 题目描述：
-
现在有一个8*8的棋盘，上面放着64个不同价值的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于100），一个人初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角。从棋盘的左上角移动到右下角的时候的，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，但是拿到的所有的礼物的价值之和不大于一个限定值limit，请设计一个算法请实现，使其能够获得不超过限制值limit的最大价值的礼物。
- 输入：
-
输入包含多个测试用例，每个测试用例共有9行，第一行是一个限制值limit<=1000，下面还有8行8列，第i行的第j列的数字代表了该处棋盘上的礼物的价值，每两个数之间用空格隔开。
- 输出：
-
对于每组测试用例，请输出你能够获得不超过限制值limit的最大价值的礼物。若没有符合条件的线路则输出-1。
- 样例输入：
-
904 2 5 1 3 8 9 74 5 2 3 7 1 8 67 2 1 8 5 9 3 62 8 9 5 6 3 1 71 2 4 5 3 7 9 63 5 7 8 9 6 2 410 8 1 4 7 5 3 97 4 6 2 1 3 9 8
- 样例输出：
-
90
#include
#include #include #include using namespace std;int limit,map[10][10];int dp[10][10][1010];int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&limit)){ for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) scanf("%d",&map[i][j]); memset(dp,0,sizeof(dp)); for(int i=8;i>=1;i--) for(int j=8;j>=1;j--) for(int k=0;k<=limit;k++){ if(k>=map[i][j]){ int tmp=0; if(i!=8 && dp[i+1][j][k-map[i][j]]>tmp) tmp=dp[i+1][j][k-map[i][j]]; if(j!=8 && dp[i][j+1][k-map[i][j]]>tmp) tmp=dp[i][j+1][k-map[i][j]]; if(tmp==0 && !(i==8 && j==8)) dp[i][j][k]=0; else dp[i][j][k]=tmp+map[i][j]; } } if(dp[1][1][limit]!=0) printf("%d\n",dp[1][1][limit]); else puts("-1"); } return 0;}