阿里云3.24笔试题

只说编程题，选择题太难了，我不会

三道题都是O(n)解法：

第一题是经典dp，每一个可以选蓝色或者黄色，有各自的得分，也可以不选，但是相邻不能同色。求最大得分

dp维护蓝、黄、不选三个状态，最后求最大值即可。

第二题是一个贪心，找到两个数组完全不同的互斥区间个数（区间内对应index的数都不能相同）

维护一个两个数组同一下标数值相等的数组，在数组前push（-1），在数组后push（n，数组的长度）

然后找到维护数组相邻下标之间有多少数，设为x，则结果加上x*(x+1)/2

第三题是一个贪心，对于每一个国家必须对应一个粮食的消耗（第一个国家除外），然后找到每一个国家需要购买粮食的地方，这个地方的代价最小即可。对于国家i，从j买，花费vec[j],则开销(i-1-j+vec[j]),对于每一个i来说，只需要让（-1-j+vec[j]）最小，取反也就是（j+1-vec[j]）最大，对于i，维持一个[1,i-1]的最大一个即可。最后模拟累加即可