首页 > > 程序设计 > C/C++ >

UVALive 6853（dp）

2018-06-17 23:45:43来源：未知阅读 ()

题意：已知有n个城市，某歌手每月进行一场演唱会，共持续c个月，可连续两个月在同一个城市。城市间的路费已给出，且已知每个城市在第k（1<=k<=c）个月举办演唱会的所得利润,求最终的最大利润。

分析：第i个月在第j个城市举办演唱会，最终可得最大利润，由此可得状态转移方程：dp[i][j] = max(dp[i][j], dp[i - 1][k] - d[k][j] + a[j].v[i])。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cstdlib>
 7 #include<cmath>
 8 using namespace std;
 9 const int MAXN = 100 + 10;
10 struct
11 {
12     int v[55];
13 }a[MAXN];
14 int d[MAXN][MAXN];
15 int dp[MAXN][MAXN];
16 int main()
17 {
18     int n;
19     scanf("%d", &n);
20     while(n--)
21     {
22         memset(d, 0, sizeof d);
23         memset(dp, 0, sizeof dp);
24         int s, c;
25         scanf("%d%d", &s, &c);
26         for(int i = 1; i <= s; ++i)
27             for(int j = 1; j <= c; ++j)
28                 scanf("%d", &a[i].v[j]);
29         for(int i = 1; i <= s; ++i)
30             for(int j = 1; j <= s; ++j)
31                 scanf("%d", &d[i][j]);
32         for(int i = 1; i <= s; ++i)
33             dp[1][i] = a[i].v[1];
34         for(int i = 2; i <= c; ++i)
35             for(int j = 1; j <= s; ++j)
36                for(int k = 1; k <= s; ++k)
37                     dp[i][j] = max(dp[i][j], dp[i - 1][k] - d[k][j] + a[j].v[i]);
38         int ans = 0;
39         for(int i = 1; i <= s; ++i)
40             ans = max(ans, dp[c][i]);
41        printf("%d\n", ans);
42     }
43     return 0;
44 }