hdu - 5074 Hatsune Miku (简单dp)

有m种不同的句子要组成一首n个句子的歌,每首歌都有一个美丽值,美丽值是由相邻的句子种类决定的,给出m*m的矩阵map[i][j]表示第i种句子和第j种句子的最大得分,一首歌的美丽值是由sum(map[i][i+1],map[i+1][i+2]....)

初始给出n个句子的值,为正就不能改变,为负表示可以替换,输出最大的美丽值.

dp[i][j]表示前i个句子且第i个句子种类为j的最大得分。下面分情况讨论.

if(p[i]>0)

　　if(p[i-1]>0) dp[i][p[i]]=dp[i-1][p[i-1]]+score[p[i-1]][p[i]];

　　else if(p[i-1]<0) dp[i][p[i]]=max(dp[i][p[i]],dp[i-1][j]+score[j][p[i]]) (j>=0&&j<=m)

else if(p[i]<0)

　　if(p[i-1]>0) dp[i][j]=max(dp[i][j],dp[i-1][p[i-1]]+score[p[i-1]][j]) (j>=0&&j<=m)

　　else if(p[i-1]<0) dp[i][j]=max(dp[i][j],dp[i-1][k]+score[j][k])(j>=0&&j<=m,k>=0&&k<=m)

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <string>

 #include <set>

 #include <functional>

 #include <numeric>

 #include <sstream>

 #include <stack>

 //#include <map>

 #include <queue>

 #include <deque>

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #define CL(arr, val)    memset(arr, val, sizeof(arr))

 #define ll long long

 #define INF 0x7f7f7f7f

 #define lc l,m,rt<<1

 #define rc m + 1,r,rt<<1|1

 #define pi acos(-1.0)

 #define L(x)    (x) << 1

 #define R(x)    (x) << 1 | 1

 #define MID(l, r)   (l + r) >> 1

 #define Min(x, y)   (x) < (y) ? (x) : (y)

 #define Max(x, y)   (x) < (y) ? (y) : (x)

 #define E(x)        (1 << (x))

 #define iabs(x)     (x) < 0 ? -(x) : (x)

 #define OUT(x)  printf("%I64d\n", x)

 #define lowbit(x)   (x)&(-x)

 #define Read()  freopen("a.txt", "r", stdin)

 #define Write() freopen("b.txt", "w", stdout);

 #define maxn 110

 #define maxv 5010

 #define mod 1000000000

 using namespace std;

 int main()

 {

     //Read();

     int t,n,m;

     int score[][],p[],dp[][];

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<=m;i++)

             for(int j=;j<=m;j++) scanf("%d",&score[i][j]);

         for(int i=;i<=n;i++) scanf("%d",&p[i]);

         memset(dp,,sizeof(dp));

         for(int i=;i<=n;i++)

         {

             if(p[i]>)

             {

                 if(p[i-]>)

                 {

                     dp[i][p[i]]=dp[i-][p[i-]]+score[p[i-]][p[i]];

                 }

                 else

                 {

                     for(int j=;j<=m;j++)

                     dp[i][p[i]]=max(dp[i][p[i]],dp[i-][j]+score[j][p[i]]);

                 }

             }

             else

             {

                 if(p[i-]>)

                 {

                     for(int j=;j<=m;j++)

                     dp[i][j]=max(dp[i][j],dp[i-][p[i-]]+score[p[i-]][j]);

                 }

                 else

                 {

                     for(int j=;j<=m;j++)

                         for(int k=;k<=m;k++)

                         dp[i][j]=max(dp[i][j],dp[i-][k]+score[k][j]);

                 }

             }

             //printf("%d\n",dp[i][j]);

         }

         int ans=;

         for(int i=;i<=m;i++)

             ans=max(ans,dp[n][i]);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

hdu - 5074 Hatsune Miku (简单dp)

最新文章

热门文章