做题感悟：开始不用标记数组把 dp 数组初始化一下用于标记但是这样因为初始化的原因就超时了，改为标记数组才过。
解题思路：记忆化搜索
这题很明显，如果用递推的方法的话必定不好写，因为在一行里可以向左做可以向右走，这样就导致不好递推，如果用记忆化方法的话就很好写了，如果单纯的只向右和下的话可以用三维标记 dp[ i ] [ j ] [ k ] (代表到达第i行第 j 列经历了 k 个负数所得到的最优值) ，这里还可以向左走，so~> 必须必须加一维方向，标记是从哪个方向得到的，放置重复走 ，即： dp [ i ] [ j ] [ k ] [ d ] 代表到达第 i 行第 j 列出现了 k 个负数从方向
d 得到的最优解。
代码：
#include<iostream>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT long long int
using namespace std ;
const INT INF = 999999999 ;
const INT MY = 10 ;
const INT MX = 75 + 5 ;
INT n ,k ;
bool vis[MX][MX][MY][MY] ;
INT dp[MX][MX][MY][MY] ,g[MX][MX] ;
INT dx[4]={1 ,0 ,0} ,dy[4]={0 ,-1 ,1} ;
void input()
{
for(INT i = 0 ;i < n ;i++)
for(INT j = 0 ;j < n ;j++)
scanf("%lld",&g[i][j]) ;
memset(vis ,false ,sizeof(vis)) ;
}
INT DP_Memory(INT x ,INT y ,INT z ,INT d)
{
if(z > k) return -INF ;
if(x==n-1 && y == n-1)
return g[x][y] ;
if(vis[x][y][z][d])
return dp[x][y][z][d] ;
vis[x][y][z][d] = true ;
INT& ans = dp[x][y][z][d] ;
ans = -INF ;
for(INT t = 0 ;t < 3 ;t++)
{
INT sx = x + dx[t] ;
INT sy = y + dy[t] ;
if(d + t == 3) continue ;
if(sx >= 0 && sy >= 0 && sx < n && sy < n)
{
INT mx = (g[sx][sy] < 0) ;
INT my = DP_Memory(sx ,sy ,z+mx ,t) ;
if(my != -INF)
ans = max(my + g[x][y] ,ans) ;
}
}
return ans ;
}
int main()
{
int cse = 1 ;
while(scanf("%lld%lld",&n ,&k) ,n+k)
{
input() ;
INT x = (g[0][0] < 0) ,ans = -INF ;
ans = DP_Memory(0 ,0 ,x ,0) ;
cout<<"Case "<<cse++<<": " ;
if(ans != -INF)
cout<<ans<<endl ;
else cout<<"impossible"<<endl ;
}
return 0 ;
}