POJ 3230 Travel

問題文

DP強化週間。

街がN個あり、すべての街の間を移動するのに必要な交通費の情報が与えられる。またi日目にjの街にいたときにもらえる金額の情報が与えられる。M回移動するとしたときに得られる最大の金額を求めよ。という問題。

dp[j][i]:=(i回移動した後に街jにいるときの最大金額)でDP。
するととなる。

以下ソース。

int dp[101][101];
int cost[100][100];
int income[100][100];
int n, m;

int main(){
  while(scanf("%d %d", &n, &m) != EOF){
    if(n == 0 && m == 0) break;
    for(int i = 0; i < n; i++)
      for(int j = 0; j < n; j++)
	scanf("%d", &cost[i][j]);
    
    for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
	scanf("%d", &income[i][j]);
	
    for(int i = 0; i < 101; i++)
      for(int j = 0; j < 101; j++)
	dp[i][j] = -INF;


    dp[0][0] = 0;
    for(int i = 0; i < m; i++){
      for(int j = 0; j < n; j++){
	for(int k = 0; k < n; k++){
	  dp[j][i + 1] = max(dp[j][i + 1], dp[k][i] - cost[k][j] + income[i][j]);
	}  
      }
    }
      
    int ans = -INF;
    for(int i = 0; i < n; i++) ans = max(ans, dp[i][m]);
    printf("%d\n", ans);
  }
  return 0;
}

原因不明のTLEが多発した。あと初期化を少し間違えてしまた。問題ちゃんと読まないと。ロジックはすぐわかったからまだいいものの、複合的な原因でACから遠ざかっている状況が浮き彫りになった。