哪些网站是做外贸生意的,网站建设所需美工,免费发布信息的网站平台,域名解析系统的英文缩写题目链接#xff1a; http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode3385 题目大意#xff1a; 妖梦要准备一个party#xff0c;所以需要许多食物#xff0c;初始化妖梦的烹饪技能为L#xff0c;每天妖梦有两种选择#xff0c;一是选择当天做L个食物 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode3385 题目大意 妖梦要准备一个party所以需要许多食物初始化妖梦的烹饪技能为L每天妖梦有两种选择一是选择当天做L个食物二是提升自己的烹饪技能为L1。 但是幽幽子非常能吃每天幽幽子都要吃Ai的食物当没食物吃后幽幽子会非常生气甚至想把妖梦批判一番。所以现在妖梦要保证做出的食物每天够幽幽子吃的情况下尽量的多。 解题过程 好久好久之前比赛的题一直没补当初知道是贪心和栈感觉这样的思维题加简单的数据结构的题非常难……也可能是直接接触的题太少吧。 题目分析 首先用栈去贪心的模拟在能保证够幽幽子吃的情况下最多能够将技能提高到几级。 假设每天都提高等级并且将天数入栈当当前剩下的食物不够幽幽子吃的话将上一次提升等级的地方换成做食物。如果还是不够幽幽子吃的话那么就是无解的。 因为提高等级是一个持久性的加成当然是越早提升越好所以每次将提高等级换做做食物的地方都是最晚的地方。 这样求解出最高可以升到几级后再去求下最大能达到多少食物。 同样效仿上面的操作每次取出最近的提升等级的地方换成做食物去维护一个最大值。 不过有可能有这样的一个情况在租个替换掉提升等级时可能某个地方替换掉提升等级后食物就不够幽幽子吃了。但是这种情况求出的结果肯定比维护的最大值要小因为现在食物不够吃了并且等级还低了那么最后算出的剩余一定是更小的。 AC代码 #include stdio.h
#include stack
using namespace std;typedef long long LL;int main() {LL N, L;while (~scanf(%lld %lld, N, L)) {LL sum 0;bool flag true;stackLL ss;for (int i 1; i N; i) {LL eat;//每天要吃的食物数scanf(%lld, eat);if (!flag)continue;ss.push(i);L;//如果当前剩余的食物不够的话去替换掉之前提升等级while (sum eat !ss.empty()) {LL t ss.top();L--;ss.pop();//将提升等级替换成做食物是很容易维护的首先让等级减一加上等级然后当从提升等级那天到至今的提升等级的加成减去sum L - (i-t);}if (sum eat) {flag false;continue;}sum - eat;}if (!flag) {printf(Myon\n);continue;}LL ans sum;//求出最大值类似上面的过程while (!ss.empty()) {LL t ss.top();L--;ss.pop();sum L - (N - t);ans max(ans, sum);}printf(%lld\n, ans);}
} 转载于:https://www.cnblogs.com/ACMFish/p/7222821.html
