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 
#include 
#include 
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;
}