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


感觉改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
维护两者差值进行dp
点赞 回复 分享
发布于 2018-08-12 12:42
顶一顶,求解答
点赞 回复 分享
发布于 2018-08-12 12:40
你这个时间复杂度是3^100吧
点赞 回复 分享
发布于 2018-08-12 12:29
想了老半天,求大佬解答
点赞 回复 分享
发布于 2018-08-12 12:28

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
仁者伍敌:服务员还要脱颖而出,这是五星级酒店吗
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务