hdu

有m种不同的句子要组成一首n个句子的歌,每首歌都有一个美丽值,美丽值是由相邻的句子种类决定的,给出m*m的矩阵map[i][j]表示第i种句子和第j种句子的最大得分,一首歌的美丽值是由sum(map[i][i+1],map[i+1][i+2]....)

初始给出n个句子的值,为正就不能改变,为负表示可以替换,输出最大的美丽值.

dp[i][j]表示前i个句子且第i个句子种类为j的最大得分。下面分情况讨论.

if(p[i]>0)

　　if(p[i-1]>0) dp[i][p[i]]=dp[i-1][p[i-1]]+score[p[i-1]][p[i]];

　　else if(p[i-1]<0) dp[i][p[i]]=max(dp[i][p[i]],dp[i-1][j]+score[j][p[i]]) (j>=0&&j<=m)

else if(p[i]<0)

　　if(p[i-1]>0) dp[i][j]=max(dp[i][j],dp[i-1][p[i-1]]+score[p[i-1]][j]) (j>=0&&j<=m)

　　else if(p[i-1]<0) dp[i][j]=max(dp[i][j],dp[i-1][k]+score[j][k])(j>=0&&j<=m,k>=0&&k<=m)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <vector>
 5 #include <cstring>
 6 #include <string>
 7 #include <algorithm>
 8 #include <string>
 9 #include <set>
10 #include <functional>
11 #include <numeric>
12 #include <sstream>
13 #include <stack>
14 //#include <map>
15 #include <queue>
16 #include <deque>
17 //#pragma comment(linker, "/STACK:102400000,102400000")
18 #define CL(arr, val)    memset(arr, val, sizeof(arr))
19 
20 #define ll long long
21 #define INF 0x7f7f7f7f
22 #define lc l,m,rt<<1
23 #define rc m + 1,r,rt<<1|1
24 #define pi acos(-1.0)
25 
26 #define L(x)    (x) << 1
27 #define R(x)    (x) << 1 | 1
28 #define MID(l, r)   (l + r) >> 1
29 #define Min(x, y)   (x) < (y) ? (x) : (y)
30 #define Max(x, y)   (x) < (y) ? (y) : (x)
31 #define E(x)        (1 << (x))
32 #define iabs(x)     (x) < 0 ? -(x) : (x)
33 #define OUT(x)  printf("%I64d
", x)
34 #define lowbit(x)   (x)&(-x)
35 #define Read()  freopen("a.txt", "r", stdin)
36 #define Write() freopen("b.txt", "w", stdout);
37 #define maxn 110
38 #define maxv 5010
39 #define mod 1000000000
40 using namespace std;
41 int main()
42 {
43     //Read();
44     int t,n,m;
45     int score[55][55],p[105],dp[105][105];
46     scanf("%d",&t);
47     while(t--)
48     {
49         scanf("%d%d",&n,&m);
50         for(int i=1;i<=m;i++)
51             for(int j=1;j<=m;j++) scanf("%d",&score[i][j]);
52         for(int i=1;i<=n;i++) scanf("%d",&p[i]);
53         memset(dp,0,sizeof(dp));
54         for(int i=2;i<=n;i++)
55         {
56             if(p[i]>0)
57             {
58                 if(p[i-1]>0)
59                 {
60                     dp[i][p[i]]=dp[i-1][p[i-1]]+score[p[i-1]][p[i]];
61                 }
62                 else
63                 {
64                     for(int j=1;j<=m;j++)
65                     dp[i][p[i]]=max(dp[i][p[i]],dp[i-1][j]+score[j][p[i]]);
66                 }
67             }
68             else
69             {
70                 if(p[i-1]>0)
71                 {
72                     for(int j=1;j<=m;j++)
73                     dp[i][j]=max(dp[i][j],dp[i-1][p[i-1]]+score[p[i-1]][j]);
74                 }
75                 else
76                 {
77                     for(int j=1;j<=m;j++)
78                         for(int k=1;k<=m;k++)
79                         dp[i][j]=max(dp[i][j],dp[i-1][k]+score[k][j]);
80                 }
81             }
82             //printf("%d
",dp[i][j]);
83         }
84         int ans=0;
85         for(int i=1;i<=m;i++)
86             ans=max(ans,dp[n][i]);
87         printf("%d
",ans);
88     }
89     return 0;
90 }