首页 > 代码库 > HDU 5074 Hatsune Miku(2014鞍山赛区现场赛E题)
HDU 5074 Hatsune Miku(2014鞍山赛区现场赛E题)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5074
解题报告:给出一个长度为n的序列,例如a1,a2,a3,a4......an,然后这个序列的美丽值就是socre[a1][a2] + socre[a2][a3] + ..... socre[an-1][an],但是这个序列里面并不是所有的数都是确定的,输入包含一些大于0的数和一些-1,-1表示这个数可以任意,但是要在m的范围内,给出socre[i][j],求这个序列最大的美丽值.
一个二维dp,dp[i][j] 的意义就是当第i个数是j的时候的前i个数的美丽值是dp[i][j],然后递推公式如下:
dp[i][j] = max(dp[i][j],dp[i-1][k] + socre[k][j]);
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 7 int T,n,m; 8 int value[55][55],note[105],dp[105][55]; 9 int main()10 {11 // freopen("in","r",stdin);12 scanf("%d",&T);13 while(T--)14 {15 scanf("%d%d",&n,&m);16 for(int i = 1;i <= m;++i)17 for(int j =1;j <= m;++j)18 scanf("%d",&value[i][j]);19 for(int i = 1;i <= n;++i)20 scanf("%d",¬e[i]);21 memset(dp,0,sizeof(dp));22 for(int i = 2;i <= n;++i)23 {24 if(note[i] == -1)25 {26 for(int j = 1;j <= m;++j)27 {28 if(note[i-1] == -1)29 for(int k = 1;k <= m;++k)30 dp[i][j] = max(dp[i][j],dp[i-1][k] + value[k][j]);31 else dp[i][j] = max(dp[i][j],dp[i-1][note[i-1]] + value[note[i-1]][j]);32 }33 }34 else35 {36 if(note[i-1] == -1)37 for(int k = 1;k <= m;++k)38 dp[i][note[i]] = max(dp[i][note[i]],dp[i-1][k] + value[k][note[i]]);39 else dp[i][note[i]] = max(dp[i][note[i]],dp[i-1][note[i-1]] + value[note[i-1]][note[i]]);40 }41 }42 int ans = 0;43 for(int i = 1;i <= m;++i)44 ans = max(ans,dp[n][i]);45 printf("%d\n",ans);46 }47 return 0;48 }
HDU 5074 Hatsune Miku(2014鞍山赛区现场赛E题)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。