本文主要是介绍hdu5074 Hatsune Miku，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
鞍山现场赛里的一道题，都说是水题，却让我花了很长时间。。。
首先我一看就知道要用dp，不过我的思路在一开始总是那么低级。。。
最开始，我想的是把任意两种音符中间间隔任意个空缺的最优值算出来，然后再扫描 s数组，直接把最优值加起来就行了。结果写了5层循环，dp数组也是3维的。估算了一下，复杂度大概在10的7次方，感觉勉强能过得。。。交了tle，现在看来，显然会tle。
第二次尝试，我还是觉得10的7次方不至于太慢，就想着怎么优化，开始是先统计最长的段的长度，递推时以这个长度为上界，这样显然效果不大。。。于是又想到了我这样递推，等于把所有情况都考虑进去了，有很多不必要的操作。。于是就想到，用记忆化搜索正好可以避免不必要的操作。可是循环还是太多，依然tle...
第三次，（这个时候受到挫败已经想不动了。。。看了题解），发现我找的最优子结构不是“最优”的，或者说，我对问题的处理太过间接了，绕了很多弯子。比较高效的最优子结构是，对于最终的长度为i的最优解，它一定是最后一个字符加上前面长度为i-1的最优解中最大的。。。。如此简单明了的最优子结构定义，为什么我一开始想的不是这个。。为什么我在tle后没有及时反思自己的思路。。。。
第一次尝试代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 55
#define MAX1 110
using namespace std;int map[MAX][MAX],dp[MAX][MAX][MAX1],s[MAX1];int main()
{/*char s[10];int n=11;itoa(n,s,2);printf("%s",s);*/int t,n,m,i,j,p,q,x,a,b,c;int front,rear,all,temp,ceil;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);for(i=1;i<=m;i++){for(j=1;j<=m;j++){scanf("%d",&a);map[i][j]=a;}}for(i=0;i<n;i++)scanf("%d",&s[i]);ceil=0;for(front=rear=0;rear<n;rear++){if(s[rear]<0&&rear==n-1){ceil=max(ceil,rear-front);break;}else if(s[rear]<0)rear++;else if(s[rear]>0){ceil=max(ceil,rear-front);front=rear;rear++;}}memset(dp,0,MAX*MAX*MAX1*4);all=0;for(i=1;i<=m;i++){for(j=1;j<=m;j++)dp[i][j][1]=map[i][j];}for(i=2;i<=ceil;i++){for(j=1;j<=m;j++){for(p=1;p<=m;p++){for(q=1;q<=m;q++){for(x=1;x<i;x++){dp[j][p][i]=max(dp[j][p][i],dp[j][q][x]+dp[q][p][i-x]);}}}}}for(front=rear=0;rear<n;){if(rear==n-1&&s[rear]<0){temp=0;for(i=1;i<m;i++){temp=max(temp,dp[s[front]][i][rear-front]);}all+=temp;front=rear;rear++;}else if(s[rear]<0){rear++;}else if(s[rear]>0){if(s[front]<0){temp=0;for(i=1;i<m;i++){temp=max(temp,dp[i][s[rear]][rear-front]);}all+=temp;}elseall+=dp[s[front]][s[rear]][rear-front];front=rear;rear++;}}printf("%d\n",all);}return 0;
}
第二次尝试代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 55
#define MAX1 110
using namespace std;int map[MAX][MAX],dp[MAX][MAX][MAX1],s[MAX1],m;int dg(int first,int last,int length)
{if(dp[first][last][length]>=0)return dp[first][last][length];int i,j,t;for(i=1;i<=m;i++){for(j=1;j<length;j++){dp[first][last][length]=max(dp[first][last][length],dg(first,i,j)+dg(i,last,length-j));}}return dp[first][last][length];
}int main()
{/*char s[10];int n=11;itoa(n,s,2);printf("%s",s);*/int t,n,i,j,p,q,x,a,b,c;int front,rear,all,temp;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);for(i=1;i<=m;i++){for(j=1;j<=m;j++){scanf("%d",&a);map[i][j]=a;}}for(i=0;i<n;i++)scanf("%d",&s[i]);/*ceil=0;for(front=rear=0;rear<n;rear++){if(s[rear]<0&&rear==n-1){ceil=max(ceil,rear-front);break;}else if(s[rear]<0)rear++;else if(s[rear]>0){ceil=max(ceil,rear-front);front=rear;rear++;}}*/memset(dp,-1,MAX*MAX*MAX1*4);all=0;for(i=1;i<=m;i++){for(j=1;j<=m;j++)dp[i][j][1]=map[i][j];}/*for(i=2;i<=ceil;i++){for(j=1;j<=m;j++){for(p=1;p<=m;p++){for(q=1;q<=m;q++){for(x=1;x<i;x++){dp[j][p][i]=max(dp[j][p][i],dp[j][q][x]+dp[q][p][i-x]);}}}}}*/for(front=rear=0;rear<n;){if(rear==n-1&&s[rear]<0&&front==0){temp=0;for(i=1;i<m;i++){for(j=1;j<=m;j++)temp=max(temp,dg(j,i,rear-front));}all=temp;break;}else if(rear==n-1&&s[rear]<0){temp=0;for(i=1;i<m;i++){temp=max(temp,dg(s[front],i,rear-front));}all+=temp;front=rear;rear++;}else if(s[rear]<0){rear++;}else if(s[rear]>0){if(s[front]<0){temp=0;for(i=1;i<m;i++){temp=max(temp,dg(i,s[rear],rear-front));}all+=temp;}elseall+=dg(s[front],s[rear],rear-front);front=rear;rear++;}}printf("%d\n",all);}return 0;
}
最终ac代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 55
#define MAX1 110
using namespace std;int map[MAX][MAX],dp[MAX1][MAX],s[MAX1];int main()
{int t,m,n,i,j,p,q,maxx;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);memset(map,0,MAX*MAX*4);for(i=1;i<=m;i++){for(j=1;j<=m;j++)scanf("%d",&map[i][j]);}memset(dp,0,MAX*MAX1*4);for(i=1;i<=n;i++)scanf("%d",&s[i]);maxx=0;for(i=2;i<=n;i++){for(j=1;j<=m;j++){if(s[i-1]>0){dp[i][j]=dp[i-1][s[i-1]]+map[s[i-1]][j];}else{for(p=1;p<=m;p++){dp[i][j]=max(dp[i][j],dp[i-1][p]+map[p][j]);}}}}for(i=1;i<=m;i++)maxx=max(maxx,dp[n][i]);printf("%d\n",maxx);}return 0;
}这篇关于hdu5074 Hatsune Miku的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
