这题是相当经典的动态规划了,类似于 01 背包问题。
定义 dp[i][j] 为,考虑前 i 个帖子,点赞数为 i 所需的最少帖子数。
用 cur[i] 表示当前帖子能造成的点赞数。
状态转移为:dp[i]j]=min(dp[i−1][j−cur[i]+1,d[i][j])
小红有n个账号,每个账号粉丝数为ai。
这天他又创建了一个新账号,他希望新账号的粉丝数恰好等于x。为此他可以向自己已有账号的粉丝们推荐自己的新账号,这样以来新账号就得到了之前粉丝的关注。
他想知道,他最少需要在几个旧账号发“推荐新账号”的文章,可以使得他的新账号粉丝数恰好为x,除此以外,他可以最多从中选择一个账号多次发“推荐新账号”的文章。
假设一个旧账号粉丝数为ai,如果仅推荐一次,那么新账号粉丝数增加⌊2ai⌋,如果多以推荐,则粉丝数增加ai
输入包含2行。
第一行两个正整数n,x(1≤n,x≤100),分别表示小红的旧账号个数,和新账号想要的粉丝数。
第二行n个正整数ai(1≤ai≤100),表示小红每个旧账号的粉丝数。
输出包含一行一个整数,表示小红最少需要向多少个旧帐号推荐新账号,如果无法做到,输出-1。
输入
5 8
1 2 3 4 10
输出
2