笔记精选

[编程题]笔记精选

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

薯队长写了n篇笔记，编号从1~n,每篇笔记都获得了不少点赞数。

薯队长想从中选出一些笔记，作一个精选集合。挑选的时候有两个规则：

1.不能出现连续编号的笔记。

2.总点赞总数最多

如果满足1，2条件有多种方案，挑选笔记总数最少的那种

输入描述:

输入包含两行。第一行整数n表示多少篇笔记。 第二行n个整数分别表示n篇笔记的获得的点赞数。   
 （0<n<=1000,    0<=点赞数<=1000)

输出描述:

输出两个整数x,y。空格分割。
 x表示总点赞数，y表示挑选的笔记总数。

示例1

输入

4
1 2 3 1

输出

4 2

算法知识视频讲解

Python

临期月亮

这个问题可以通过动态规划来解决。我们定义两个数组dp和count，其中：

dp[i]表示在前i篇笔记中能获得的最多点赞数。
count[i]表示在前i篇笔记中能获得dp[i]个点赞数所需要的最少笔记数。

动态规划的状态转移方程如下：

如果不选第i篇笔记，则有dp[i] = dp[i-1]，并且count[i] = count[i-1]。
如果选第i篇笔记，则有dp[i] = dp[i-2] + likes[i]（第i篇笔记的点赞数），并且count[i] = count[i-2] + 1。

初始化：

dp[0] = likes[0]，count[0] = 1
dp[1] = max(likes[0], likes[1])，count[1] = 1 if likes[0] < likes[1] else 1

最终结果为dp[n-1]和count[n-1]。

def select_notes(n, likes):
    if n == 0:
        return 0, 0
    if n == 1:
        return likes[0], 1

    # 初始化dp和count数组
    dp = [0] * n  # 在前 i 篇笔记中能获得的最多点赞数
    count = [0] * n  # 在前 i 篇笔记中能获得 dp[i] 个点赞数所需要的最少笔记数

    dp[0] = likes[0]
    count[0] = 1

    dp[1] = max(likes[0], likes[1])
    count[1] = 1  # 不能选连续的，只能二选一，选大的

    for i in range(2, n):
        if dp[i - 1] >= dp[i - 2] + likes[i]:  # 只是>不行，无法使笔记数最小
            dp[i] = dp[i - 1]
            count[i] = count[i - 1]
        else:
            dp[i] = dp[i - 2] + likes[i]
            count[i] = count[i - 2] + 1

    return dp[-1], count[-1]


# 输入处理
n = int(input())
likes = list(map(int, input().split()))

发表于 2024-07-02 21:59:37 回复(0)

Python

喵喵喵喵喵喵喵喵喵喵喵喵喵喵

参考力扣打家劫舍，不仅要计算出抢得的财物数量，还需要计算抢的房间数量最小

n = int(input())

li = input().split()
li = [int(l) for l in li]

if n == 0:
print(0, 0)
elif n == 1:
print(li[0], 1)
else:
dp = [0 for _ in range(n)]
dp[0] = li[0]
dp[1] = max(li[:2])
num = [0 for _ in range(n)]
num[0] = 1
num[1] = 1
for i in range(2, n):
if dp[i-1] < (dp[i-2] + li[i]):
dp[i] = dp[i-2] + li[i]
num[i] = num[i-2] + 1
else:
dp[i] = dp[i-1]
num[i] = num[i-1]
print(dp[-1], num[-1])

发表于 2023-07-18 10:58:12 回复(0)

Python

ΔtZ.

动态规划

n = int(input())
a = list(map(int,input().split()))
dp  = [0]*(n+1)
flag = [0]*(n+1)
dp[1] = a[0]
flag[1] = 1
for i in range(2,n+1):
    num = a[i-1]
    dp[i] = max(num+dp[i-2],dp[i-1])
    if dp[i]==dp[i-1]:
        flag[i] = flag[i-1]
    else:
        flag[i] = flag[i-2]+1
print(str(dp[n])+' '+str(flag[n]))

编辑于 2020-08-11 21:21:51 回复(0)

Python

我不想当大白菜

考察点：动态规划

相比于经典的打家劫舍问题，多了个对选择的个数的限制。对每个位置的状态用dp_star[i]来表示在[0,i]上能获得的最大点赞数。在计算总点赞数数组dp_star的基础上，多加一个动态规划数组dp_count来统计在每个位置i上取到最大点赞数时的笔记的个数。

最大点赞数数组的状态转移方程为：f(i) = max(f(j)+nums[i],f(i-1)), j in [0,i-2]

其中j in[0,i-2]是取i处的笔记时的最大点赞数，还要与不取i处的笔记时的最大点赞总数dp_star[i-1]进行比较，取最大的为当前点赞数，如果最大值是取了当前位置的笔记得到的，那么笔记的计数也需要加一。

N = int(input())
nums = list(map(int, input().split()))

def getMaxStar(N, nums):
    dp_star = [0 for _ in range(N)]
    dp_count = [0 for _ in range(N)]
    dp_star[0], dp_count[0] = nums[0], 1
    dp_star[1], dp_count[1] = nums[1] if nums[1] > nums[0] else nums[0], 1
    for i in range(2, N):
        # get nums[i]
        for j in range(0, i-1):
            if dp_star[j] + nums[i] > dp_star[i]:
                dp_star[i] = dp_star[j] + nums[i]
                dp_count[i] = dp_count[j] + 1
        # not get nums[i], compare dp_star[i-1]
        if dp_star[i-1] > dp_star[i]:
            dp_star[i] = dp_star[i-1]
            dp_count[i] = dp_count[i-1]
    # get max star num with min count
    max_val, min_cnt = 0, 10000
    for val, cnt in zip(dp_star, dp_count):
        if val > max_val:
            max_val = val
            min_cnt = cnt
        elif val == max_val:
            if cnt < min_cnt:
                min_cnt = cnt

    print(max_val, min_cnt)

getMaxStar(N,nums)

发表于 2020-07-06 22:34:39 回复(0)