Yuan
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
zoj 3385 贪心 ★★★
/**/
/*
题意:每一天,可升级1,或者做L个食物。但每天至少要有ai的食物存量
问N天后的最多食物 N<=10^5
很容易想到N^2的DP 肯定TLE
用贪心做!
N天都不升级,结果为NL
前面t天用来升级,结果为(N-t)(L+t) = NL + t(N-L-t) 最后结果可以增加
一种贪心思路:
应该尽量早的升级,不得以才放弃升级,改成准备食物,当然最后几天可能都准备食物比较好
用一个栈来记录实现
*/
#include
<
cstdio
>
#include
<
stack
>
using
namespace
std;
int
main()
{
//
freopen("in","r",stdin);
int
N;
int
x,L;
while
(
~
scanf(
"
%d%d
"
,
&
N,
&
L))
{
long
long
ans
=
0
,sum
=
0
;
stack
<
int
>
S;
for
(
int
i
=
1
;i
<=
N;i
++
)
{
scanf(
"
%d
"
,
&
x);
if
(ans
!=-
1
)
{
sum
=
sum
+
x;
S.push(i);
while
(
!
S.empty()
&&
ans
<
sum)
{
//
直接ans+=会wa 可能溢出的问题
ans
=
ans
+
(L
+
S.size()
-
1
)
-
(i
-
S.top());
//
还要-(i-S.top()) 因为由于S.top()这一天没有升级,所以(S.top(),i]用的L减1了
S.pop();
}
if
(S.empty()
&&
ans
<
sum)ans
=-
1
;
}
}
if
(ans
==-
1
)puts(
"
Myon
"
);
else
{
while
(
!
S.empty()
&&
(L
+
S.size()
-
1
)
>
(N
-
S.top()))
{
ans
=
ans
+
(L
+
S.size()
-
1
)
-
(N
-
S.top());
S.pop();
}
printf(
"
%lld\n
"
,ans
-
sum);
}
}
return
0
;
}
发表于 2010-08-24 15:13
_Yuan
阅读(135)
评论(0)
编辑
收藏
引用
所属分类:
OJ解题报告
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
SRM 239 HiddenTriangles ★★★★
CodeForces 59E 以边为状态bfs ★★★★
TCO'10 Wildcard Round 500pt CalculationCards
zoj 3462 bitset
SRM 496 PalindromfulString 容斥写法 ★★★★
CodeForces 57D
CodeForces 55D 数位统计 记忆化搜索 跟pre有关 ★★★★
CodeForces 55E Very simple problem
zoj 3455 统计出现次数 判断相等 用l[i]记录字母出现i次的个数 ★★★★
zoj 3354 映射 环 计数 ★★★
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
常用链接
我的随笔
我的评论
我参与的随笔
随笔分类
Dp(27)
(rss)
OJ解题报告(153)
(rss)
OThers(17)
(rss)
TopCoder
(rss)
计算几何(2)
(rss)
枚举(4)
(rss)
数据结构(6)
(rss)
数论(5)
(rss)
搜索(2)
(rss)
贪心(4)
(rss)
图论(10)
(rss)
学习笔记(6)
(rss)
学习总结(19)
(rss)
组合数学(3)
(rss)
Links
Lord Li
Lord zeus
搜索
最新评论
1. re: 双向BFS[未登录]
博主,只用一个队列不就可以解决你第一个问题了吗
--jason
2. re:nvgagkguaioguaiiananfajfofajiosfgoasoajgia[未登录]
cscdcuis
--1
3. re: zoj 3436 逆推 搜
评论内容较长,点击标题查看
--ZH
4. re: zoj 2318 计算几何 spfa判负环
写得好!
--ipqhjjybj
5. re: Poj 1066
@杨书鉴
你写的排序好像不对啊。。。
--小猊