学步园

FatMouse and Cheese

题意

     以前写解题报告的时候很少涉及题意，但是这道题由于理解错了题意WA了三次！~~~

     在一个n阶方阵A中，Aij表示在第i行第j列的位置处所有的cheese数目。老鼠起始位置为(0,0)，老鼠在方阵中移动的规则是：<1>、每次最多沿着水平(或垂直)方向跳k格；<2>、每次所跳至的格中cheese数目要比当前位置处得多。求老鼠所能得到的cheese的最大数目。

/*<br /> dfs+dp，也可以说是记忆化搜索<br /> 起初的时候我用dfs做的，TLE，觉得无从剪枝<br /> 网上看了看发现使用记忆化搜索来做的，个人认为记忆化搜索的内涵其实就是dfs+dp<br /> 直接用dp很很难去做的，比如此题中的dp[i][j]表示以(i,j)为"起点"所能得到的最优值<br /> 因为是起点，那么去进行状态转移的时候就显得很难下手，几乎是不可能的！<br /> 但是若采用dfs的方式来打表实现状态转移(记忆化搜索)，就显得简单了很多.<br /> */<br /> #include<iostream><br /> using namespace std;<br /> int n,k,block[101][101],dp[101][101],dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};<br /> int dfs(int x,int y){<br /> if(dp[x][y])<br /> return dp[x][y];//只需"回忆"一下，而不需重复性的搜索<br /> int max=0;<br /> for(int i=0;i<4;i++)<br /> for(int j=1;j<=k;j++){<br /> int r,c;<br /> r=x+j*dx[i];c=y+j*dy[i];<br /> if(r>=0 && r<n && c>=0 && c<n && block[r][c]>block[x][y]){<br /> int tmp=dfs(r,c);<br /> if(tmp>max) max=tmp;<br /> }<br /> }<br /> dp[x][y]=max+block[x][y];<br /> return dp[x][y];<br /> }</p> <p>int main(){<br /> while(cin>>n>>k,n+1||k+1){<br /> for(int i=0;i<n;i++)<br /> for(int j=0;j<n;j++){<br /> cin>>block[i][j];dp[i][j]=0;<br /> }<br /> dfs(0,0);<br /> cout<<dp[0][0]<<endl;<br /> }<br /> return 0;<br /> }