首页 > 代码库 > 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 }
View Code

 

HDU 5074 Hatsune Miku(14鞍山区域赛 E)DP