今日头条第三题编程题,有些出来的大佬吗,看看我这个的问题


感觉改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;

}



#笔试题目##字节跳动#
全部评论
你输入写错了啊,每一行是两个数x和y,是怎么过样例的。。
点赞 回复 分享
发布于 2018-08-12 12:41
想了老半天,求大佬解答
点赞 回复 分享
发布于 2018-08-12 12:28
你这个时间复杂度是3^100吧
点赞 回复 分享
发布于 2018-08-12 12:29
顶一顶,求解答
点赞 回复 分享
发布于 2018-08-12 12:40
维护两者差值进行dp
点赞 回复 分享
发布于 2018-08-12 12:42

相关推荐

评论
点赞
收藏
分享
牛客网
牛客企业服务