Yuan
|
首頁
|
發(fā)新隨筆
|
發(fā)新文章
|
聯(lián)系
|
聚合
|
管理
zoj 3385 貪心 ★★★
/**/
/*
題意:每一天,可升級(jí)1,或者做L個(gè)食物。但每天至少要有ai的食物存量
問N天后的最多食物 N<=10^5
很容易想到N^2的DP 肯定TLE
用貪心做!
N天都不升級(jí),結(jié)果為NL
前面t天用來升級(jí),結(jié)果為(N-t)(L+t) = NL + t(N-L-t) 最后結(jié)果可以增加
一種貪心思路:
應(yīng)該盡量早的升級(jí),不得以才放棄升級(jí),改成準(zhǔn)備食物,當(dāng)然最后幾天可能都準(zhǔn)備食物比較好
用一個(gè)棧來記錄實(shí)現(xiàn)
*/
#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+=會(huì)wa 可能溢出的問題
ans
=
ans
+
(L
+
S.size()
-
1
)
-
(i
-
S.top());
//
還要-(i-S.top()) 因?yàn)橛捎赟.top()這一天沒有升級(jí),所以(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
;
}
發(fā)表于 2010-08-24 15:13
_Yuan
閱讀(138)
評(píng)論(0)
編輯
收藏
引用
所屬分類:
OJ解題報(bào)告
只有注冊(cè)用戶
登錄
后才能發(fā)表評(píng)論。
【推薦】100%開源!大型工業(yè)跨平臺(tái)軟件C++源碼提供,建模,組態(tài)!
相關(guān)文章:
SRM 239 HiddenTriangles ★★★★
CodeForces 59E 以邊為狀態(tài)bfs ★★★★
TCO'10 Wildcard Round 500pt CalculationCards
zoj 3462 bitset
SRM 496 PalindromfulString 容斥寫法 ★★★★
CodeForces 57D
CodeForces 55D 數(shù)位統(tǒng)計(jì) 記憶化搜索 跟pre有關(guān) ★★★★
CodeForces 55E Very simple problem
zoj 3455 統(tǒng)計(jì)出現(xiàn)次數(shù) 判斷相等 用l[i]記錄字母出現(xiàn)i次的個(gè)數(shù) ★★★★
zoj 3354 映射 環(huán) 計(jì)數(shù) ★★★
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
常用鏈接
我的隨筆
我的評(píng)論
我參與的隨筆
隨筆分類
Dp(27)
(rss)
OJ解題報(bào)告(153)
(rss)
OThers(17)
(rss)
TopCoder
(rss)
計(jì)算幾何(2)
(rss)
枚舉(4)
(rss)
數(shù)據(jù)結(jié)構(gòu)(6)
(rss)
數(shù)論(5)
(rss)
搜索(2)
(rss)
貪心(4)
(rss)
圖論(10)
(rss)
學(xué)習(xí)筆記(6)
(rss)
學(xué)習(xí)總結(jié)(19)
(rss)
組合數(shù)學(xué)(3)
(rss)
Links
Lord Li
Lord zeus
搜索
最新評(píng)論
1.?re: 雙向BFS[未登錄]
博主,只用一個(gè)隊(duì)列不就可以解決你第一個(gè)問題了嗎
--jason
2.?re:nvgagkguaioguaiiananfajfofajiosfgoasoajgia[未登錄]
cscdcuis
--1
3.?re: zoj 3436 逆推 搜
評(píng)論內(nèi)容較長,點(diǎn)擊標(biāo)題查看
--ZH
4.?re: zoj 2318 計(jì)算幾何 spfa判負(fù)環(huán)
寫得好!
--ipqhjjybj
5.?re: Poj 1066
@楊書鑒
你寫的排序好像不對(duì)啊。。。
--小猊
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 _Yuan
久久精品国产2020
|
中文字幕一区二区三区久久网站
|
欧美777精品久久久久网
|
久久国产免费观看精品3
|
韩国无遮挡三级久久
|
国产午夜精品理论片久久
|
一本一道久久a久久精品综合
|
午夜视频久久久久一区
|
久久精品视频一
|
99久久精品国产免看国产一区
|
久久99精品国产
|
久久精品中文字幕一区
|
亚洲国产精品一区二区久久hs
|
久久精品国产只有精品2020
|
久久无码人妻精品一区二区三区
|
久久精品久久久久观看99水蜜桃
|
国产精品天天影视久久综合网
|
久久精品无码专区免费
|
久久99精品国产麻豆
|
亚洲精品成人网久久久久久
|
久久午夜伦鲁片免费无码
|
久久人人爽人人爽人人片AV麻豆
|
久久婷婷五月综合成人D啪
|
久久夜色精品国产噜噜亚洲AV
|
久久99精品国产麻豆婷婷
|
久久婷婷五月综合97色
|
久久久久久曰本AV免费免费
|
精品免费久久久久国产一区
|
91久久精一区二区三区大全
|
久久精品卫校国产小美女
|
四虎影视久久久免费
|
色综合久久最新中文字幕
|
日日躁夜夜躁狠狠久久AV
|
一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区
|
久久亚洲AV成人出白浆无码国产
|
国产99久久九九精品无码
|
久久久精品2019免费观看
|
国产精品久久久久久久app
|
久久九九免费高清视频
|
久久国产精品免费
|
四虎国产精品免费久久久
|