题目

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

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

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

2.总点赞总数最多 

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

输入描述：

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

输出描述：

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

输入例子：

4
1 2 3 1

输出例子：

4 2

分析

“打家劫舍”动规题的衍生，可以用dp[i]来表示前i篇笔记所有选择方式获得的最多点赞数，cnt[i]代表达到dp[i]所选取的笔记数。

状态转移

那么状态转移方程分成以下三种情况

首先以dp[i]最大化优先，

如果dp[i-2]+value[i]大于dp[i-1]，那么在前一篇和当前篇中选择当前篇

如果dp[i-1]大于dp[i-2]+value[i]，那么在前一篇和当前篇中选择前一篇

而当dp[i-2]+value[i]等于dp[i-1]，那么在两种方案中选择笔记数量更少的方案

初始化

dp[1] = value[1] , cnt[1] = 1

dp[2] = max(value[1],value[2]) , cnt[2] = 1

Python代码

def select_notes(n,a):
    a = [0]+a
    dp = [0] * 1010 # dp[i]表示选择前i个笔记的最大点赞数
    cnt = [0] * 1010 # cnt[i] 表示针对前i个笔记选择的笔记个数

    # 第一篇
    dp[1] = a[1]
    cnt[1] = 1
    # 第二篇
    if a[2] > a[1]:
        dp[2] = a[2]
    else:
        dp[2] = a[1]
    cnt[2] = 1

    for i in range(3,n+1):
        if dp[i-1] > dp[i-2] + a[i]: # 选择上一篇而不是这一篇
            dp[i] = dp[i-1]
            cnt[i] = cnt[i-1]
        elif dp[i-1] < dp[i-2] + a[i]: # 选择这一篇和上上一篇
            dp[i] = dp[i-2] + a[i]
            cnt[i] = cnt[i-2] + 1
        else: # 相等选择个数更少的
            dp[i] = dp[i-1]
            cnt[i] = min(cnt[i-2]+1,cnt[i-1])
    # print("dp : ",dp[1:n+1])
    # print("cnt : ",cnt[1:n+1])
    return dp[n],cnt[n]

def main():
    n = 9
    a = [610,312,540,775,314,897,300,212,146]
    num,cnt = select_notes(n,a)
    print(num,cnt)

if __name__ == "__main__":
    main()