ZOJ 2846 Traverl(DP)

题意:有一个旅行家,在N个城市之间旅行,每天旅行家可以呆在当前城市或者去下一个城市,两两城市之间旅行有一个代价C[i][j], ,如果第i天在第j个城市里面那么有一个收益值P[i][j],求旅行家能够得到的最大收益值.

思路:还是比较简单的DP,阶段无非就是第i天和第j个城市.

设dp[i][j]为第i天在第j个城市的最大总收益值.

那么dp[i][j] = max(dp[i - 1][k] + C[k][j] + P[i][j]) 1<=  K <= n.

base case: dp[0][1] = 0初始旅行家在第1个城市.

#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
const int MAX = 101;

int main(int argc, char const *argv[]){
	int dp[MAX][MAX];
	int cost[MAX][MAX];
	int profit[MAX][MAX];
	int n, m;
	while(scanf("%d%d", &n, &m) == 2){
		if(!n && !m)break;
		memset(dp, 0xf6, sizeof(dp));
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= n; ++j){
				scanf("%d", &cost[i][j]);
			}
		}

		for(int i = 1; i <= m; ++i){
			for(int j = 1; j <= n; ++j){
				scanf("%d", &profit[i][j]);
			}
		}

		dp[0][1] = 0;
		for(int i = 1; i <= m; ++i){
			for(int j = 1; j <= n; ++j){
				for(int k = 1; k <= n; ++k){
					dp[i][j] = max(dp[i][j], dp[i - 1][k] - cost[k][j] + profit[i][j]);
				}
			}
		}

		printf("%d\n", *max_element(dp[m] + 1, dp[m] + n + 1));
	}
	return 0;
}

ZOJ 2846 Traverl(DP),布布扣,bubuko.com

ZOJ 2846 Traverl(DP)

原文：http://blog.csdn.net/zxjcarrot/article/details/22894301