每天只能吃1次糖果理论上昨天吃了今天就不能吃但给自己k次机会在昨天吃了糖果的情况下今天仍然连续吃糖果。第一行输入 两个整数n和k表示拿到的进货计划表的天数和最多打破原则的次数。第二行n个整数a1a2an其中ai表示接下来第i天糖果专卖店的糖果的美味值输出表示小美能吃到的糖果美味值之和的最大值用动态规划c++实现并注释

#include #include #include using namespace std;

int main() { int n, k; cin >> n >> k; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<vector> dp(n, vector(2)); // dp[i][0/1]表示第i天未/已吃糖果的情况下的最大美味值 dp[0][0] = 0; dp[0][1] = a[0]; for (int i = 1; i < n; i++) { // 未吃糖果 dp[i][0] = max(dp[i-1][0], dp[i-1][1]); // 前一天未/已吃糖果的最大美味值 // 已吃糖果 if (i > 1 && k > 0) { // 如果前一天也吃了糖果且还有机会打破原则 dp[i][1] = max(dp[i-1][0] + a[i], dp[i-2][1] + a[i]); // 分别考虑打破原则和不打破原则的情况 k--; // 使用一次打破原则的机会 } else { dp[i][1] = dp[i-1][0] + a[i]; // 只能不打破原则 } } cout << max(dp[n-1][0], dp[n-1][1]); // 最后一天未/已吃糖果的最大美味值即为答案 return 0; }