学步园

好久没有做题目了，最近刚开始玩ubuntu爱不释手啊。导致我的A题大业都停滞不前啊，还好今天终于有接着做题了。今天早上看了这个POJ3230一推敲是一个动归题，状态也很好确定

f[i][j]表示第i天在第j个城市能得到的最多的钱。但是还是wa了好多次，好桑心啊。原来是因为第一天的情况没有考虑清楚，第一天肯定是从第一个城市出发的，所以上一个城市的起始点肯定是第一个城市，已经无需遍历了。而以后的几天之需要遍历前一天所在的城市，每次都得出最优值就可以了。代码上可以做一个空间的优化，我嫌麻烦就没有优化。

题目链接：点击打开链接

/*Source Code

Problem: 3230		User: Bearox
Memory: 528K		Time: 16MS
Language: G++		Result: Accepted
Source Code*/
#include<cstdio>
#include<cstring>
#define N 105

int exp[N][N], inc[N][N], f[N][N];
int main()
{
    int n, m;
    int i, j, k;
    while(scanf("%d%d", &n, &m) != EOF)
    {
	if(n == 0 && m == 0) return 0;
	for(i = 1; i <= n; ++i)
	    for(j = 1; j <= n; ++j)
		scanf("%d", &exp[i][j]);
	for(i = 1; i <= m; ++i)
	    for(j = 1; j <= n; ++j)
		scanf("%d", &inc[i][j]);
	memset(f, 0, sizeof(f));
	for(i = 1; i <= m; ++i)
	{
	    for(j = 1; j <= n; ++j)
	    {
		if(i == 1) {f[i][j] = inc[i][j] - exp[1][j]; continue;}
		int max = f[i - 1][1] - exp[1][j];
		for(int k = 2; k <= n; ++k)
		    max = f[i - 1][k] - exp[k][j] > max? f[i - 1][k] - exp[k][j] : max;
		f[i][j] = max + inc[i][j];
	    }
	}
	int max = f[m][1]; 
	for(j = 2; j <= n; ++j)
	    max = f[m][j] > max? f[m][j] : max;
	printf("%d\n", max);
    }
    return 0;
}