UFO

UFO

时间: 2ms        内存:64M

描述:

UFO likes traveling by bike very much. He intends to travel this summer. Due to lack of money, he must bring things and exchange them with others. When he arrives in a city, he sells everything he has and buys new things. Then he travels to another city, sells his items and buys new ones. In this problem you will have to find the total amount of money UFO will gain on the optimal tour. On a tour he can go to some city more than once, and he must finish his tour in some cities. Also there is a starting city for his tour and the number of inter-city travels he wants to do in his tour.

输入:

The input file contains several test cases. The first line is N: the number of test cases. Then follows N cases. The description of each case is given below: Each case starts with four integers C (2 <= C <= 100), the number of cities, and the cities are numbered from 1 to C, S (1 <= S <= C), the identifier of the starting city, E (1 <= E <= C-1), the number of cities his tour can end at, and T (1 <= T <= 1000), the number of inter-city travels he wants to do. Follow C lines with C non-negative integers which are no more than 1000. The jth integer of the ith line will describe the profit he earns when he goes from city i to city j by selling things. As he does not want to make a trip to a city he is already, the ith integer of the ith line will always be 0. Note that going from city i to city j can have a different profit than going from city j to city i. After there will be a line with E integers, the identifier of the cities he can end his tour.

输出:

For each input case produce one line of output, the total profit he can earn in the corresponding tour.

示例输入:

1
3 1 2 2
0 3 5
5 0 1
9 2 0
2 3

示例输出:

7

提示:

参考答案(内存最优[1256]):

#include <stdio.h>
#include <string.h>
#define maxs(a,b) (a>b?a:b)

int d[105][105];
int dp[1005][105];
int endll[105];

int main(){
    int ca;
    scanf("%d", &ca);
    while (ca--){
        int n, s, e, t;
        scanf("%d%d%d%d", &n, &s, &e, &t);
        for (int i=1; i<=n; i++)
            for (int j =1; j<=n; j++)
                scanf("%d", &d[i][j]);
        for (int i=1; i<=e; i++)
            scanf("%d", &endll[i]);
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=n; i++)
            dp[1][i] = d[s][i];
        for (int k=2; k<=t; k++){
            for (int i=1; i<=n; i++)
                for (int j=1; j<=n; j++)
                    dp[k][i] = maxs(dp[k][i], dp[k-1][j] + d[j][i]);
        }
        int res =  0;
        for (int i=1; i<=e; i++)
            res = maxs(res, dp[t][endll[i]]);
        printf("%d\n", res);
    }
}

参考答案(时间最优[164]):

#include <stdio.h>
#include <string.h>
#define maxs(a,b) (a>b?a:b)

int d[105][105];
int dp[1005][105];
int endll[105];

int main(){
    int ca;
    scanf("%d", &ca);
    while (ca--){
        int n, s, e, t;
        scanf("%d%d%d%d", &n, &s, &e, &t);
        for (int i=1; i<=n; i++)
            for (int j =1; j<=n; j++)
                scanf("%d", &d[i][j]);
        for (int i=1; i<=e; i++)
            scanf("%d", &endll[i]);
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=n; i++)
            dp[1][i] = d[s][i];
        for (int k=2; k<=t; k++){
            for (int i=1; i<=n; i++)
                for (int j=1; j<=n; j++)
                    dp[k][i] = maxs(dp[k][i], dp[k-1][j] + d[j][i]);
        }
        int res =  0;
        for (int i=1; i<=e; i++)
            res = maxs(res, dp[t][endll[i]]);
        printf("%d\n", res);
    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注