大家好,又见面了,我是全栈君。
题目链接:题意:
给定一个m*m的矩阵mp。然后给定一个长度为n的序列
sum= mp[a[1]][a[2]]+……+mp[a[n-1]][a[n]];
假设a[i]小于0的话则a[i]能够为1~m之间的随意一个数,求sum的最大值
我们能够枚举第i个位置
然后dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[k][j]) 表示第i个位置在j的最大值;
然后分两种情况
假设a[i]是一个确定的数的话 dp[i][a[i]]=max( dp[i][a[i]],dp[i-1][j]+mp[j][a[i]] )
假设不确定的话 就仅仅能枚举a[i]了 dp[i][k]=max(dp[i][k],dp[i-1][j]+mp[j][k]);
这两种情况都是建立在前一个位置已经确定了值的情况下;
代码例如以下:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 55; int mp[maxn][maxn]; int dp[maxn*2][maxn],a[maxn*2]; int main() { int t,n,m; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); } for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,-1,sizeof(dp)); if(a[1]!=-1) dp[1][a[1]]=0; else for(int i=1;i<=m;i++) dp[1][i]=0; for(int i=2;i<=n;i++){ for(int j=1;j<=m;j++){ if(dp[i-1][j]!=-1){//假设前一项已经确定 if(a[i]!=-1) dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][j]+mp[j][a[i]]); else{ for(int k=1;k<=m;k++) dp[i][k]=max(dp[i][k],dp[i-1][j]+mp[j][k]); } } } } /*************** cout<<" debug "<<endl; for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++) cout<<dp[i][j]<<" "; cout<<endl; } cout<<"***********"<<endl; **************/ int maxn = -1000; for(int i=1;i<=m;i++) maxn=max(dp[n][i],maxn); printf("%d\n",maxn); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115913.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...