4.21 淘天笔试

选择题我们就不说了

编程题三道

第一道

小红买糖果，有n种糖果，数组a【n】，a【i】表示这种糖果单价为i，美味度为a【i】，

然后小红只买一种糖果，

问美味度不小于k的买糖果所花的钱最少，1<=k<=x，

输入n，x

ai......

输出x个数值，第i个数值表示k=1的时候所花的最小价格

我第一题刚开始以为买糖果的时候只买一包，然后就用dp来存前面的最大美味度

但是实际上是可以买好多包。

第二道

字符串权值的方案数，字符串权值是指字符串中相邻两字符相等的字串的对数（一对只有两个字符）。

给你一个字符串，求出这个字符串取出字串的权值为k的方案数。

输入 string n k（n是字符串的长度）

输出方案数

我做的是枚举，当然是会超时的，但是写完这个之后我觉得好像可以用dp吧，但是没时间写了。

第三道

超级舰队？

小美是一个公司的老板，下面有好多员工，员工有一个直接上司，上司的上司也是上司，

超级舰队是指这个团队里面每个员工都没有上司在这个团队里面。

求出超级舰队的最大工作量。

输入n（总员工），k（超级舰队的员工数）

a【n-1】数组，a【i】表示第i个员工的上司的位置在第a【i】个位置

b【n】数组，b【i】表示第i个员工的工作量

输出超级舰队的最大工作量

鼠鼠这道题就看了一眼就没时间做了。。。。。。