首页 > 代码库 > hdu5074 Hatsune Miku

hdu5074 Hatsune Miku

2024-11-05 18:45:02   210人阅读

题意：有一个m*m的矩阵，每个位置都有一个值，然后给你一个序列，-1的位置可以替换，然后求出序列的最大值

思路：问题的关键在于dp状态的定义，（训练的时候没想出来，以为贪心，但不知道怎么贪，dp也不知道怎么转移，我竟然还想到用最短路做，可能脑子坏掉了，还是太菜了）

定义dp【i】【j】中i代表目前用了几个数，就是进行到a【i】的第几个了，j代表最后一个数用的是几，然后分情况讨论a[i]，a[i-1]与0的关系.最后扫一下dp【n】【i】的最大值

得出结果

下面是代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn=105;
 6 int dp[maxn][maxn];
 7 int mp[maxn][maxn];
 8 int a[maxn];
 9 
10 int main()
11 {
12     int t;
13     scanf("%d",&t);
14     while(t--){
15         int n,m;
16         scanf("%d %d",&n,&m);
17         for(int i=1;i<=m;i++){
18             for(int j=1;j<=m;j++){
19                 scanf("%d",&mp[i][j]);
20             }
21         }
22         for(int i=1;i<=n;i++)
23             scanf("%d",&a[i]);
24         memset(dp,0,sizeof(dp));
25         for(int i=2;i<=n;i++){
26             if(a[i]>0&&a[i-1]>0){
27                 dp[i][a[i]]=dp[i-1][a[i-1]]+mp[a[i-1]][a[i]];
28             }
29             else if(a[i-1]<0&&a[i]>0){
30                 for(int k=1;k<=m;k++){
31                     dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][k]+mp[k][a[i]]);
32                 }
33             }
34             else if(a[i-1]<0&&a[i]<0){
35                 for(int j=1;j<=m;j++){
36                     for(int k=1;k<=m;k++){
37                         dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[k][j]);
38                     }
39                 }
40             }
41             else if(a[i-1]>0&&a[i]<0){
42                 for(int k=1;k<=m;k++){
43                     dp[i][k]=max(dp[i][k],dp[i-1][a[i-1]]+mp[a[i-1]][k]);
44                 }
45             }
46         }
47         int cnt=0;
48         for(int i=1;i<=m;i++)
49             cnt=max(cnt,dp[n][i]);
50         printf("%d\n",cnt);
51     }
52     return 0;
53 }

 

hdu5074 Hatsune Miku


联系
我们