UVALive 6853（dp），uvalive6853dp

UVALive 6853（dp），uvalive6853dp

題意：已知有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 }