大家好，又见面了，我是全栈君。
题目链接：题意：
给定一个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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115913.html原文链接：https://javaforall.net
