首页 > 技术交流 > 招银前端-AB同事选最大身高的问题

招银前端-AB同事选最大身高的问题

头像
chen_CHEN976
编辑于 2017-09-18 14:41:59
回复2 | 赞 0 | 浏览1717

[编程|14分] 团建活动

时间限制:1秒
空间限制:32768K

题目描述

公司最近组织团队建设活动,其中一个游戏有A、B两名参赛者参加,游戏规则如下:有m个不同身高的同事站成一排,A、B两个参赛者依次从最左边开始选择一名或者两名同事出列(A先开始),直到所有同事都被选择完为止,最终计算两名参赛者所选择的同事的身高总和,总身高更高的人获胜。假设两名参赛者都足够聪明,请判定第一名参赛者A是输还是赢?

输入描述:

输入的第1行为1个正整数,代表同事数量m; 输入的第2行为m个正整数,代表每位同事的身高,中间用空格分隔。

输出描述:

如果参赛者A赢则输出true,输或打平则输出false。

示例1

输入

3
2 3 4

输出

true

本来准备做成DP的结果做成了动态规划。。
A了以后发现代码还有问题
有没有做DP的DALAO给个思路?
。。。。代码分割。。。。。。
/**

  • Created by CBB on 2017/9/13.
    /
    /*
  • Created by CBB on 2017/9/13.
    */
    var readline = require('readline');
    const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal:false
    });
    var n =-1;
    var dp =[];
    rl.on('line', function(line){ // javascript每行数据的回调接口
    if(n<0){
    n++;
    }else{

    var arr = line.split(" ");
     var len = arr.length;
     var total =0;
     for(var i =0;i<len;i++){
         arr[i] = Number(arr[i]);
         total += arr[i];
     }
    
     var totalA = fn(arr,arr.length);
     var totalB = total -totalA;
     if(totalA>totalB){
         console.log("true")
     }else{
         console.log("false");
     }
     dp = [];
     n =-1;

    }
    });
    function fn(arr,n){
    //计算出A能能尽力拿到的比B多的时候 拿多少
    dp[1] = arr[0];
    dp[2] = arr[0]+arr[1];
    dp[3] = arr[0]+arr[1];
    var tmp = arr[0] + arr[3];
    var tmp2 = arr[0]+arr[1];
    dp[4] = Math.max(tmp,tmp2);
    if(n <=4){

    return dp[n];

    }
    //n-4 n-3 n-2 n-1四个数字
    var tmp1 = arr[n-1];
    var tmp2 = arr[n-1] + arr[n-2];
    var tmp3 = arr[n-2] + arr[n-3];

    var a = arr[n-1] + arr[n-4];
    var b = arr[n-4] + arr[n-3];
    var tmp4 = Math.max(a,b);

    dp[n] = fn(arr,n-1)+tmp1 + fn(arr,n-2) + tmp2 + fn(arr,n-3) +tmp3 +fn(arr,n-4) + tmp4;

    return dp[n];
    }

2条回帖

回帖
加载中...
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋