首页 > 代码库 > [HDU 5074] Hatsune Miku (动态规划)

[HDU 5074] Hatsune Miku (动态规划)

2024-07-28 18:16:32   222人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5074

题目大意是给你m个note，n个数，得分是v[a[i]][a[i+1]]的总和，如果说a[i]是负数的话代表可以放人一个note，否则就只能放他给的note号。

问：最大的得分是多少？

 

我先写了记忆化搜索函数

dp(i,j)代表到第i个位置，放标号为j的note

那么

如果说a[i+1]<0，那么dp(i,j) = max( dp(i,j) , dp(i+1,k)+v[j][k] );

否则dp(i,j) = dp(i+1,a[i+1]) + v[j][a[i+1]];

然后改成递推呗~

 

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

 

[HDU 5074] Hatsune Miku (动态规划)


联系
我们