POJ3230——Travel

Travel

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4185   Accepted: 1758

Description

One traveler travels among cities. He has to pay for this while he can get some incomes.

Now there are n cities, and the traveler has m days for traveling. Everyday he may go to another city or stay there and pay some money. When he come to a city ,he can get some money. Even when he stays in the city, he can also get the next day‘s income.
All the incomes may change everyday. The traveler always starts from city 1.

Now is your turn to find the best way for traveling to maximize the total income.

Input

There are multiple cases.

The first line of one case is two positive integers, n and m .n is the number of cities, and m is the number of traveling days. There follows n lines, one line n integers. The j integer in the i line is the expense of traveling from city i to city j. If
i equals to j it means the expense of staying in the city.

After an empty line there are m lines, one line has n integers. The j integer in the i line means the income from city j in the i day.

The input is finished with two zeros.

n,m<100.

Output

You must print one line for each case. It is the max income.

Sample Input

3 3
3 1 2
2 3 1
1 3 2

2 4 3
4 3 2
3 4 2

0 0

Sample Output

8

Hint

In the Sample, the traveler can first go to city 2, then city 1, and finish his travel in city 1. The total income is:

-1+4-2+4-1+4=8;

Source

简单dp题,我们用dp[i][j] 表示到第i天,在城市j时的最大收益,所以方程就很容易写出来了

dp[i][j] = max(dp[i-1][k] - mat[k][j] + w[i][j])

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>  

using namespace std;

int dp[105][105];
int mat[105][105];
int w[105][105];

int main()
{
	int n, m;
	while (~scanf("%d%d", &n, &m))
	{
		if (!n && !m)
		{
			break;
		}
		memset ( dp, -0x3f3f3f3f, sizeof(dp) );
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				scanf("%d", &mat[i][j]);
			}
		}
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				scanf("%d", &w[i][j]);
			}
		}
		dp[0][1] = 0;
		for (int i = 1; i <= n; i++)
		{
			dp[1][i] = dp[0][1] - mat[1][i];
		}
		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] - mat[k][j] + w[i][j]);
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i++)
		{
			ans = max(ans, dp[m][i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}
时间: 10-31

POJ3230——Travel的相关文章

UVA 1048 - Low Cost Air Travel(最短路)

UVA 1048 - Low Cost Air Travel 题目链接 题意:给定一些联票,在给定一些行程,要求这些行程的最小代价 思路:最短路,一张联票对应几个城市就拆成多少条边,结点表示的是当前完成形成i,在城市j的状态,这样去进行最短路,注意这题有坑点,就是城市编号可能很大,所以进行各种hash 代码: #include <cstdio> #include <cstring> #include <vector> #include <queue> #in

Travel(最短路)

Travel The country frog lives in has nn towns which are conveniently numbered by 1,2,…,n1,2,…,n. Among n(n−1)2n(n−1)2 pairs of towns, mm of them are connected by bidirectional highway, which needs aa minutes to travel. The other pairs are connected b

Travel(HDU 5441 2015长春区域赛 带权并查集)

Travel Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2404    Accepted Submission(s): 842 Problem Description Jack likes to travel around the world, but he doesn’t like to wait. Now, he is tr

ural 1286. Starship Travel

1286. Starship Travel Time limit: 1.0 secondMemory limit: 64 MB It is well known that a starship equipped with class B hyperengine is able to travel from any planet to any other planet. But your starship got severe damage in the last travel and now i

hdu 4571 Travel in time (Floyd+记忆化搜索)

Travel in time Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1853    Accepted Submission(s): 374 Problem Description Bob gets tired of playing games, leaves Alice, and travels to Changsha alo

travel hamburg

The area west of Hamburg's central railway station is mainly a shopping area with the streets Spitaler Straße and Mönckebergstraße, leading to Hamburg's town hall. The building behind the city hall is Hamburg's House of Commerce (Börse). Between the

poj 3230 Travel(dp)

Description One traveler travels among cities. He has to pay for this while he can get some incomes. Now there are n cities, and the traveler has m days for traveling. Everyday he may go to another city or stay there and pay some money. When he come

hdu5431 Travel

Problem Description Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are n cities and m bidirectional roads connecting the cities. Jack hates waiting too long on the bus, but he

pat1030. Travel Plan (30)

1030. Travel Plan (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue A traveler's map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help