小美因乐于助人的突出表现获得了老师的嘉奖。老师允许小美从一堆n个编号分别为1,2...,n的糖果中选择任意多个糖果作为奖励(每种编号的糖果各一个),但为了防止小美一次吃太多糖果有害身体健康,老师设定了一个限制:如果选择了编号为﹔的糖果,那么就不能选择编号为i-1,i-2,i+1, i+2的四个糖果了。在小美看来,每个糖果都有一个对应的美味值,小美想让她选出的糖果的美味值之和最大!作为小美的好朋友,请你帮帮她!
时间: 2023-05-26 19:07:47 浏览: 97
思路:
此题是一道DP题目,我们设dp[i]为前i个糖果所选能得到的最大美味值。
我们注意到,若选择第i个糖果,那么第i-1个糖果肯定不能选了,且当i-1被选的时候,i-2就不能被选了,所以我们要根据i-1选择与否分成两种情况。
情况1:选择了第i-1个糖果,那么i-2就不能选,i-3是可以被选的。
情况2:没有选择第i-1个糖果,那么i-2和i-3都是可以被选的。
所以状态转移方程为:
dp[i] = max(dp[i-1],dp[i-2]+a[i]),(选了i-1、没选i-2)或者(没选i-1、选了i-2)
其中a[i]为每个糖果的美味值。
代码:
相关问题
小美刚刚学习了十六进制,她觉得很有趣,想到是不是还有更大的进制呢 在十六进制中,用 A 表示10、F 表示 15。 如果扩展到用Z表示35岂不是可以表示36进制数了嘛! 输入 输入2行,第一行包含一个正整数N. 第二行包含一个正整数R. 输出 输出1行,为N的R进制表示。c++写出
以下是C++代码实现:
```c++
#include <iostream>
#include <string>
using namespace std;
int main() {
int n, r;
cin >> n >> r;
string ans = ""; // 用字符串来存储结果
while (n) {
int d = n % r;
char c;
if (d >= 10) { // 大于等于10的数字用字母表示
c = d - 10 + 'A';
} else {
c = d + '0';
}
ans = c + ans;
n /= r;
}
cout << ans << endl;
return 0;
}
```
输入的第一行是要转换的数字N,第二行是进制R。程序使用了字符串来存储结果,依次将N除以R并取余,把余数转换成字符表示,最后将结果字符串倒序输出即可。需要注意的是,当余数大于等于10时,用字母表示,比如A表示10,B表示11,以此类推。
id name 1 Elon 2 Donny 3 Carey 4 Karin 5 Larisa 现在小美想改变相邻俩学生的座位(若学生人数为奇数,则无需改变最后一位同学的座位),现在需要你编写SQL输出小美想要的的结果。
假设当前学生座位信息已存储在名为"seats"的表中,包含学生编号(id)和座位编号(seat_number)两个字段,可以使用以下SQL语句实现相邻俩学生的座位交换:
UPDATE seats s1, seats s2
SET s1.seat_number = s2.seat_number, s2.seat_number = s1.seat_number
WHERE s1.id = s2.id - 1 AND s1.id % 2 = 1;
该语句将表中相邻编号为奇数的学生的座位进行交换。例如,如果原来的座位编号为1, 2, 3, 4, 5,则执行上述语句后,可能得到的新座位编号为2, 1, 4, 3, 5。