posts - 218, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZJU2846

Posted on 2007-07-12 02:16 魔のkyo 阅读(256) 评论(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());
    }
}
只有注册用户登录后才能发表评论。