美团3.25笔试

#美团#
第一题模拟一个栈，一遍过。
第二题用dp做的，dp(n) = max( dp(n-1) , a[n-1] + dp(n-3) ) ，两种情况取最大值。然后第一次提交的时候超时了，没想到好的办法，于是就定义了全局变量，把每次dp的值保存下来，这样重复的dp就不用再算了，因为它有dp(n-1)和dp(n-3)嘛，肯定会有重复的，重复的就直接查数组，然后ac了。
第三题是找巧克力的最大数目，只过了81%，也是超时了，但是不知道怎么改。我的做法就是从0开始遍历，直到重量超过了那个规定值，然后退出循环，输出count。核心代码贴下面，大佬们看看怎么改。
void solve(long long int i,int n,int* edge) {        //i是背包的容量
    long long int sum = 0;                //sum代表巧克力重量之和
    int count = -1;
    while(sum<=i && count<n){
        count++;
        sum+=pow(edge[count],2);
    }
    cout<<count<<' ';
}

第四题跳了，但是感觉花点时间能做出来了，但是我来不及了，先去做了第五题。

第五题没过，一开始的思路错了，发现错误之后来不及改了，我一开始是打算，先不管k次破例的机会，就当正常的dp做，相当于是 dp(n) =max( dp(n-1) , a[n-1] + dp(n-2))，然后对数组从大到小排序，选出其中前k的数加上去，得到最终结果。
然后这样有问题，因为原本可能选了1，3，5三天吃糖果，然后恰好2，4两天的值也是前k大的，那就会导致连续5天都在吃糖果，需要破例4次，但我只用了2次。
所以k次破例的机会也得放在dp里面一起算，但是来不及改了。
--------------------------------------------------------------
代码题做的还是不太熟练，而且这次dp考的好多，第一题做的其实也很笨，看到有人直接用stack做的，但是我没学过这个容器，我只学过怎么构造stack😓😓不过还好也就是多花了点时间，好歹做出来了。