题目
薯队长写了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()
