首页 > 试题广场 >

队列得分

[编程题]队列得分

热度指数：2192 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小M和大M要通过选择元素组成队列进行得分pk。目前存在队列S1,S2,S3...Sn,每个元素包括2个正整数属性set和value.从中选出任意K个元素S[i1],S[i2]...S[ik],保证顺序不变即i1 < i2 < i3< ... < ik,组成新的队列P1,P2,P3......Pk.我们通过一个机制评价队列的好坏:

Base=P1.value+P2.value+...Pk.value,

Bonus=10*t;t为新队列中Pi.set=P(i+1).set的i个数.

最终得分Score=Base-Bonus;求Score的最大值和取最大值时新队列元素个数的最小值.

输入描述:

第一行包含一个数N(0 < N <= 500)

接下来N行每一行两个数表示S1,S2,...,Sn的set和value值  (0 < set,value <= 20)

输出描述:

Score的最大值和新队列元素个数的最小值

示例1

输入

输出

31 4

说明

选S1,S3,S4,S5

算法知识视频讲解

Python

ElonB

""""
动态规划求解，或DFS
参考@无心2019 代码，设dp[n]为选中Si且以Si结尾的最大值，
dp[n] = max{ dp[0]+Score, dp[1]+Score, ... ,dp[n-1]+Score, Base }
"""


class node:
    def __init__(self, set, value):
        self.set = set
        self.value = value


if __name__ == "__main__":
    N = int(input())
    S = []
    for _ in range(N):
        a, b = map(int, input().strip().split())
        S.append(node(a, b))
    dp, cnt = [], []
    for j in range(N):
        t_max, t_cnt = 0, 0
        for i in range(j):
            tmp = dp[i] - 10 * (1 if S[i].set == S[j].set else 0)
            if tmp > t_max:
                t_max = tmp
                t_cnt = cnt[i]
            elif tmp == t_max:
                t_cnt = min(t_cnt, cnt[i])
        dp.append(t_max + S[j].value)
        cnt.append(t_cnt + 1)
    ans_max, ans_cnt = 0, 0
    for i in range(N):
        if ans_max < dp[i]:
            ans_max = dp[i]
            ans_cnt = cnt[i]
        elif ans_max == dp[i]:
            ans_cnt = min(ans_cnt, cnt[i])
    print(ans_max, ans_cnt)

编辑于 2019-07-16 17:41:35 回复(0)