B3628 机器猫斗恶龙(贪心详解)

2024-07-10 08:24| 来源: 网络整理| 查看: 265

题目描述机器猫出门斗恶龙了！他需要通过 n 个关卡。每个关卡要么是与怪物战斗，扣除一定的血量；要么是营地，给机器猫增加一定的血量。在旅途中，机器猫任意时刻的血量不能低于或等于 0。问机器猫至少需要多少的初始血量，才能完成任务。血量为正整数。输入格式第一行，一个正整数 n，表示关卡数量。第二行，共 n 个整数 ai 输出格式仅一行，一个正整数，表示机器猫需要的初始血量。在这里插入图片描述思路:什么情况才需要使得初始化的血更多呢,那就是补的血不够用了,所以这个题目,我们倒着分析,把所以扣血的情况加上,如果说补的血大于这些扣的血,那么后面的部分就不用看了,否则,后面欠下的这些血量也应该由一开始给,我们这里假设一开始的血是0,方便计算:

#include #include #include using namespace std; int arr[100005]; int n,ans; int sum; int main() { cin >> n; for (int i = 1; i > arr[i]; arr[0] = 0; for (int i = n; i>= 0; i--) { if (arr[i]

【本文地址】

公司简介

联系我们