2064 - 旅行
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.
题目输入
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.
题目输出
You must print one line for each case. It is the max income.
输入/输出样例
题目输入
3 3 3 1 2 2 3 1 1 3 2 2 4 3 4 3 2 3 4 2 0 0
题目输出
8
提示
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;
C语言解答
#include <stdio.h> #include <string.h> #include <limits.h> int main(){ int m, n, i, j, k, maxIcomes, tmp, flag; int pay[128][128], incomes[128][128], maxIcomesEveryDayAndCity[2][128]; while (1){ scanf("%d%d", &n, &m); if (n==0 && m==0){ break; } for (i = 1; i <= n; i++){ for (j = 1; j <= n; j++){ scanf("%d", &pay[i][j]); } } for (i = 1; i <= m; i++){ for (j = 1; j <= n; j++){ scanf("%d", &incomes[i][j]); } } memset(maxIcomesEveryDayAndCity, -128, sizeof(maxIcomesEveryDayAndCity)); maxIcomesEveryDayAndCity[0][1] = 0; flag = 0; for (i = 1; i <= m; i++){ flag = !flag; for (j = 1; j <= n; j++){ for (k = 1; k <= n; k++){ tmp = maxIcomesEveryDayAndCity[!flag][k] + incomes[i][j] - pay[k][j]; if (tmp > maxIcomesEveryDayAndCity[flag][j]){ maxIcomesEveryDayAndCity[flag][j] = tmp; } } } } maxIcomes = INT_MIN; for (i = 1; i <= n; i++){ if (maxIcomesEveryDayAndCity[flag][i] > maxIcomes){ maxIcomes = maxIcomesEveryDayAndCity[flag][i]; } } printf("%d\n", maxIcomes); } return 0; }
C++解答
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int MAX = 100; int cost[MAX+2][MAX+2]; int income[MAX+2][MAX+2]; int ans[MAX+2][MAX+2]; int main() { int n, m; int temp; while (scanf("%d%d", &n, &m) && n && m) { memset(income, 0 ,sizeof(income)); memset(cost, 0 ,sizeof(cost)); memset(ans, 0, sizeof(ans)); 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", &income[i][j]); } for (int i = 1; i <= n; i++) ans[1][i] = income[1][i] - cost[1][i]; for (int i = 2; i <= m; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) { ans[i][j] = max(ans[i][j], ans[i-1][k] + income[i][j] - cost[k][j]); } int max_ans = 0; for (int i = 1; i <= n; i++) max_ans = max(max_ans, ans[m][i]); printf("%d\n", max_ans); } return 0; }
提示
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;