题解 AT3881 【[ARC090A] Candies】

看到dalao们都用DP写这道题，萌新不得不弱弱地发声：“这难道不是一道DFS题吗？”

实际上，我认为这道题目就是赤裸裸的深度优先搜索！唯一要注意的是n为0的时候的特判。

code:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[41][101];
//bool f[41][41];
int maxx;
void dfs(int x,int y,int sum)
{
    if(x<1||x>2||y<1||y>n) return;
    if(x==2&&y==n) maxx=max(maxx,sum);//maxx取最大值
    if(x<2) dfs(x+1,y,sum+a[x+1][y]);//搜索
    dfs(x,y+1,sum+a[x][y+1]);
}
int main()
{
	//ios::sync_with_stdio(false);
	int i,j;
	cin>>n;
	for(i=1;i<=2;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	dfs(1,1,a[1][1]);
	cout<<maxx;//输出
    //system("pause");
	return 0;
}