1 条题解
-
0
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // 输入处理 int n; cin >> n; vector<int> alcohol(n + 1); // 用1-based索引,方便计算 for (int i = 1; i <= n; ++i) { cin >> alcohol[i]; } // 动态规划数组定义 // dp[i][k] 表示前i个瓶子,最后连续喝了k瓶(k=0:没喝, k=1:连续1瓶, k=2:连续2瓶)的最大酒量 vector<vector<long long>> dp(n + 1, vector<long long>(3, -1e18)); // 初始化为极小值,代表不可能的状态 dp[0][0] = 0; // 初始状态:前0瓶没喝,酒量为0 // 状态转移 for (int i = 1; i <= n; ++i) { // 第i瓶没喝:前面可以是任何状态,取最大值 dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]}); // 第i瓶喝了,且是连续第1瓶:说明第i-1瓶没喝 if (dp[i-1][0] != -1e18) { dp[i][1] = dp[i-1][0] + alcohol[i]; } // 第i瓶喝了,且是连续第2瓶:说明第i-1瓶是连续第1瓶 if (dp[i-1][1] != -1e18) { dp[i][2] = dp[i-1][1] + alcohol[i]; } } // 最终结果是前n瓶所有状态的最大值 long long max_amount = max({dp[n][0], dp[n][1], dp[n][2]}); cout << max_amount << endl; return 0; }
- 1
信息
- ID
- 2580
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
粤公网安备44195502000169号