思路:
与上一篇棋盘寻宝不同的是加了一个限制条件,即不超过最大上限的最大值,很有点背包的味道,但是有与背包问题不同的是,背包里面物品可以选和不选,而这里要走下去,就必须得把棋盘上此点的礼物给拿着,但是如果超过了限制,这走不到此点,那么此点的最大值就变为0;
AC code
#include<stdio.h> #include<string.h> int map[8][8]; int dp[8][8][10010]; int main() { int i,j,l; int limte; int temp; while(scanf("%d",&limte)!=-1) { for(i=0;i<8;i++) for(j=0;j<8;j++) scanf("%d",&map[i][j]); memset(dp,0,sizeof(dp)); for(i=7;i>=0;i--) for(j=7;j>=0;j--) for(l=0;l<=limte;l++) if(l>=map[i][j]) { temp=0; if(i!=7&&dp[i+1][j][l-map[i][j]]>temp) temp=dp[i+1][j][l-map[i][j]]; if(j!=7&&dp[i][j+1][l-map[i][j]]>temp) temp=dp[i][j+1][l-map[i][j]]; if(temp==0&&!(i==7&&j==7))/*当不在i==7&&j==7的位置上时,如果temp=0,说明到此处时,装上map[i][j]必超过l,故无法到达此处, 则dp[i][j][l]=0*/ dp[i][j][l]=0; else dp[i][j][l]=temp+map[i][j]; } if(dp[0][0][limte]==0) printf("-1\n"); else printf("%d\n",dp[0][0][limte]);/*从底向上,逐次求解*/ } return 0; }