首页 > 代码库 > HDU 5074 Hatsune Miku(14鞍山区域赛 E)DP
HDU 5074 Hatsune Miku(14鞍山区域赛 E)DP
题意:给定一个序列 有些位数未知,给你如果两个数连续所得到的能量,问你怎么安排数字使得总能量最大
解题思路:dp,只与上一个字母有关。
解题代码:
1 // File Name: e.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月22日 星期三 12时16分10秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 int dp[200][60];28 int mp[60][60];29 int main(){30 int t; 31 scanf("%d",&t);32 while(t--)33 {34 memset(mp,0,sizeof(mp));35 memset(dp,-1,sizeof(dp));36 int n , m ; 37 scanf("%d %d",&n,&m);38 for(int i = 1;i <= m;i ++ )39 for(int j = 1;j <= m ;j ++)40 scanf("%d",&mp[i][j]);41 int t;42 scanf("%d",&t);43 dp[1][t] = 0 ;44 if(t == -1)45 for(int i = 1;i <= m;i ++)46 dp[1][i] = 0 ; 47 for(int i = 2;i <= n;i ++)48 {49 scanf("%d",&t);50 if(t == -1)51 {52 for(int j = 1; j <= m ;j ++)53 {54 if(dp[i-1][j] != -1)55 for(int s = 1;s <= m ;s ++)56 dp[i][s] = max(dp[i][s],dp[i-1][j] + mp[j][s]);57 }58 }else {59 for(int s = 1; s <= m; s ++)60 {61 if(dp[i-1][s] != -1)62 dp[i][t] = max(dp[i][t],dp[i-1][s] + mp[s][t]);63 }64 }65 //for(int j = 1;j <= m;j ++)66 }67 int mx = -1;68 for(int i = 1;i <= m;i ++)69 if(dp[n][i] > mx)70 mx = dp[n][i];71 printf("%d\n",mx);72 73 }74 return 0;75 }
HDU 5074 Hatsune Miku(14鞍山区域赛 E)DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。