/*
为什么我的输出不正确呢？
ans[i][j]  表示第i天在第j个城市
b[i][j]    表示第i天在第j个城市的收入
a[i][j]    表示从i到j的费用

ans[i][j] = max{ ans[i-1][k] + b[i][j] - a[k][j] }

3 3
3 1 2
2 3 1
1 3 2

2 4 3
4 3 2
3 4 2

0 0
此例中，ans[][]=
1 3 2 （3）
5 3 4 （5）
6 8 5 （8）
为使income达到最大，则1-2-1-2为最佳路线 
*/

#include <iostream>
#include <stdio.h>
using namespace std;

int a[105][105],b[105][105],ans[105][105];
int n,m;
int find(int i)//找第i行最大元素的下标
{
	int max=-1,index;
	for(int j=1;j<=n;j++)
	{
		if(ans[i][j]>max)
		{
			max=ans[i][j];
			index=j;
		}
	}
	return index;
}

void print()
{
	int sum=0,pre=1,index;
	for(int i=1;i<=m;i++)
	{
		index=find(i);
		sum+=b[i][index]-a[pre][index];
		pre=index;
	}
	printf("%d\n",sum);
}

int main()
{
	register int i,j,k;
	int max,tem;//n city, m days
	while(scanf("%d%d",&n,&m)&&(n||m))
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&a[i][j]);//cost

		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&b[i][j]);//income

		for(i=0;i<=m;i++)
			for(j=0;j<=n;j++)
				ans[i][j]=0;
		
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
			{
				max=-10000;
				for(k=1;k<=n;k++)
				{
					tem=ans[i-1][k] + b[i][j] - a[k][j];
					if(max<tem)
						max=tem;
				}
				ans[i][j]=max;
			}

		print();
	}
	return 0;
}

• Re:哎，出发地是城市1，我又忘了处理了。应该这样子： (1048) 123454321 2007-07-29 13:06:32