Posted on 2007-07-12 02:16
魔のkyo 阅读(286)
评论(0) 编辑 收藏 引用
/*
max_gain[1][loc]=gain[1][1][loc] 题目规定The traveler always start from city 1.
max_gain[day][loc]=max{ max_gain[day-1][from]+gain[day][from][loc] } 1<day<=m
*/
#include <iostream>
using namespace std;
#define DEBUG
#define gain(day,from,to) (M2[day][to]-M1[from][to])
int M1[101][101],M2[101][101];//输入存储
int max_gain[101][101];//计算最优值
int path[101][101];//记录最优解
int n,m;
void in(int arr[101][101],int x,int y)
{
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
scanf("%d",&arr[i][j]);
}
}
}
int solve()
{
for(int loc=1;loc<=n;loc++){
max_gain[1][loc]=gain(1,1,loc);
path[1][loc]=1;
}
for(int day=2;day<=m;day++){
for(int loc=1;loc<=n;loc++){
max_gain[day][loc]=max_gain[day-1][1]+gain(day,1,loc);
path[day][loc]=1;
for(int from=2;from<=n;from++){
if(max_gain[day-1][from]+gain(day,from,loc) > max_gain[day][loc]){
max_gain[day][loc]=max_gain[day-1][from]+gain(day,from,loc);
path[day][loc]=from;
}
}
}
}
int max=max_gain[m][1],max_index;
for(int j=2;j<=n;j++){
if(max_gain[m][j]>max){
max=max_gain[m][j];
max_index=j;
}
}
#ifdef DEBUG
int loc=max_index;
printf("Day%d,traveller was stay in city %d.\n",m,loc);
for(int day=m-1;day>0;day--){
loc=path[day+1][loc];
printf("Day%d,traveller was stay in city %d.\n",day,loc);
}
#endif
return max;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF && (n||m)){
in(M1,n,n);
in(M2,m,n);
printf("%d\n",solve());
}
}