题目背景:
——————————————————————————————————————————
这道题很简单,会发现n居然啊在9以内?!
那不是直接DFS就完事了???
题目思路:
———————————————————————————————————————————
先用一个DFS确定第一条路径,再在第一条路径的约束下
用dp方法做出第二条路径的最优解!
然后加上第一条路径的结果,答案取最大值即可
AC代码如下:
————————————————————————————————————————————
#include<bits/stdc++.h>
#define int long long
const long long maxn=2e2+10;
using namespace std;
int n;
int ans;
int dp[maxn][maxn],a[maxn][maxn],tmp[maxn][maxn];
void check(int x)
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j] = max(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
ans=max(ans,x+dp[n][n]);
}
void DFS(int x,int y,int cnt)
{ if(x > n || y> n)return ;
a[x][y] = 0;
if(x == n && y == n){
check(cnt);
a[x][y]=tmp[x][y];
return ;
}
DFS(x+1,y,cnt+a[x+1][y]);
DFS(x,y+1,cnt+a[x][y+1]);
a[x][y]=tmp[x][y];
}
signed main()
{
cin>>n;
int x,y,t;
while(cin>>x>>y>>t && x!=0 && y!=0 && t!=0){
a[x][y]=t;
tmp[x][y]=t;
}
DFS(1,1,a[1][1]);
cout<<ans;
return 0;
}
共 3 条回复
错误代码啊
20分???????????????????????????????????
老朱居然卡在了这道题,我不理解??!!