今日头条第三题编程题,有些出来的大佬吗,看看我这个的问题
感觉改bfs思路也是一样的,好像也可以写一个二维代价的dp,然后在所有里头找dp[i][i]的最大值,但是这个dfs哪里错了,样例可以过,但是肯定会超时,n=100,复杂度3^100
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int n;
int x[105],y[105];
int max_score;
void dfs(int idx,int a,int b,int team){
if(idx==n){
if(team>max_score && a==b){
max_score = team;
}
return ;
}
//对于一个牌,有a取,b取和都不取三种选择
dfs(idx+1,a+x[idx],b,team+y[idx]); //a取
dfs(idx+1,a,b+x[idx],team+y[idx]);
dfs(idx+1,a,b,team);
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%d",x+i);
for(int i=0;i<n;i++)
scanf("%d",y+i);
max_score = 0;
dfs(0,0,0,0);
printf("%d\n",max_score);
}
return 0;
}
#笔试题目##字节跳动#