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
閱讀(138)
評論(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
博問
Chat2DB
管理
常用鏈接
我的隨筆
我的評論
我參與的隨筆
隨筆分類
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
@楊書鑒
你寫的排序好像不對啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
91性高湖久久久久
|
国产亚洲精久久久久久无码77777
|
老色鬼久久亚洲AV综合
|
AV色综合久久天堂AV色综合在
|
情人伊人久久综合亚洲
|
亚洲精品97久久中文字幕无码
|
久久永久免费人妻精品下载
|
久久久久国色AV免费看图片
|
亚洲午夜久久久久久久久电影网
|
国产高潮国产高潮久久久91
|
狼狼综合久久久久综合网
|
一本久久综合亚洲鲁鲁五月天
|
AV无码久久久久不卡蜜桃
|
久久国产免费直播
|
久久精品国产亚洲Aⅴ香蕉
|
久久久av波多野一区二区
|
久久亚洲精品国产精品婷婷
|
国产99久久九九精品无码
|
久久水蜜桃亚洲av无码精品麻豆
|
色欲综合久久躁天天躁
|
精品国产乱码久久久久久郑州公司
|
久久精品成人免费国产片小草
|
亚洲AV成人无码久久精品老人
|
精品久久久久久国产免费了
|
国产亚洲精久久久久久无码
|
伊色综合久久之综合久久
|
久久综合狠狠综合久久激情
|
国产成年无码久久久久毛片
|
一本久久知道综合久久
|
波多野结衣久久一区二区
|
亚洲国产成人久久一区WWW
|
久久久久亚洲精品无码网址
|
9191精品国产免费久久
|
国产精品免费久久
|
国内精品久久久久久久coent
|
国产精品欧美久久久天天影视
|
久久久久无码国产精品不卡
|
欧美亚洲国产精品久久蜜芽
|
亚洲精品国产成人99久久
|
国产精品成人无码久久久久久
|
精品国产91久久久久久久a
|