#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 60
int n, m;
int board[N][N], pnt[N*N], dp[N*N];

int main( ){
	int i, j, k, ans;
	int u, v;
	while ( scanf( "%d%d", &n, &m ) != EOF ){
		for ( i = 0; i < n; i++ ) for ( j = 0; j < n; j++ ) scanf( "%d", &board[i][j] );
		ans = 0;
		for ( k = 0; k < m; k++ ){
			memset( pnt, -1, sizeof(pnt) );
			memset( dp, 0, sizeof(dp) );
			for ( i = 0; i < n; i++ ){
				for ( j = 0; j < n; j++ ){
					u = i*n+j;
					dp[u] += board[i][j];
					if ( j+1 < n ){
						v = u+1;
						if ( dp[v] < dp[u] ){
							pnt[v] = u;
							dp[v] = dp[u];
						}
					}
					if ( i+1 < n ){
						v = u+n;
						if ( dp[v] < dp[u] ){
							pnt[v] = u;
							dp[v] = dp[u];
						}
					}
				}
			}
			if ( dp[n*n-1] < 0 ) break;
			ans += dp[n*n-1];
			for ( u = n*n-1; u != -1; u = pnt[u] ){
				i = u/n;
				j = u%n;
				board[i][j] = 0;
			}
		}
		printf( "%d\n", ans );
	}
}

• 很疑惑 为什么dp会wa (0) gouxudong19 2010-11-03 13:46:27
  • Re:很疑惑 为什么dp会wa 难道是题意理解错了 请大家指教指教 (0) gouxudong19 2010-11-03 13:47:08
• Re:这样DP为什么WA (89) Dereky 2012-03-18 10:23:03