清醒了一点后我又写了一道黄色DP题,做出来了,还行,开心不少了...
中途暴露出一些问题
1、深搜过程中既然用了二维数组,那么深搜时就应该用二维循环取最优解,而不是只从最后一行中进行一维循环取最优解。
2、dfs递归的过程中应该用dfs!!!不应该像个智障一样的忘了用dfs,直接用dp数组忘了递归了。
Code
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#define int long long
using namespace std;
int a[30],m[30][30],dp[30][30],bef[30],N,M;
int dfs(int step,int no)
{
if(dp[step][no]!=-1)return dp[step][no];
if(step==1)return dp[step][no]=a[no];
int DFS=0;
for(int i=1;i<=N;i++)//from i
for(int j=1;j<=step-1;j++)
{
if(i==no)continue;//可以省略这行
if(m[i][no]==0)continue;
if(dp[j][i]+a[no]>DFS)
DFS=dfs(j,i)+a[no],bef[no]=i;
}
return dp[step][no]=DFS;
}
void befdfs(int no)
{
if(no==-1)return;
befdfs(bef[no]);
if(no==M)
cout<<no;
else
cout<<no<<' ';
return;
}
signed main()
{
cin>>N;
for(int i=1;i<=N;i++)cin>>a[i];
for(int i=1;i<=N-1;i++)
{
for(int j=i+1;j<=N;j++)
{
cin>>m[i][j];
//m[j][i]=m[i][j];
}
}
memset(dp,-1,sizeof(dp));
memset(bef,-1,sizeof(bef));
//尝试定义:最多允许访问i并以j为结尾的最优解是dp[i][j],题目未要求i和j所以答案是max{dp[i][j]};
int ans=-1,ansj;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(dfs(i,j)>ans)
{
ans=dfs(i,j);
ansj=j;
}
M=ansj;
befdfs(ansj);
cout<<endl<<ans<<endl;
return 0;
}
标签:30,no,int,P2196,dfs,DP,include,dp
From: https://www.cnblogs.com/gongkai/p/17814351.html