蒟蒻的题解

题目背景：

——————————————————————————————————————————

这道题很简单，会发现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;

}