#美团# 第一题模拟一个栈,一遍过。第二题用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😓😓不过还好也就是多花了点时间,好歹做出来了。