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
香蕉久久av一区二区三区
|
91精品国产9l久久久久
|
欧洲国产伦久久久久久久
|
亚洲国产一成久久精品国产成人综合
|
久久人人爽人人爽人人片AV东京热
|
久久婷婷五月综合色99啪ak
|
久久久无码精品亚洲日韩按摩
|
国产91久久精品一区二区
|
99久久综合狠狠综合久久
|
亚洲欧美日韩久久精品
|
天天爽天天爽天天片a久久网
|
久久夜色精品国产www
|
久久久久亚洲AV成人网人人软件
|
成人国内精品久久久久一区
|
久久96国产精品久久久
|
99久久精品国产一区二区三区
|
久久这里有精品
|
中文字幕久久欲求不满
|
久久久久久亚洲Av无码精品专口
|
久久综合日本熟妇
|
精品国产一区二区三区久久蜜臀
|
久久九九精品99国产精品
|
久久久久久国产精品美女
|
久久精品国产福利国产琪琪
|
9久久9久久精品
|
久久久久亚洲av无码专区喷水
|
狠狠色婷婷久久一区二区
|
亚洲午夜福利精品久久
|
久久久久亚洲爆乳少妇无
|
国产精品欧美亚洲韩国日本久久
|
国产一区二区三精品久久久无广告
|
色欲久久久天天天综合网精品
|
区久久AAA片69亚洲
|
中文字幕精品久久
|
欧美亚洲国产精品久久高清
|
亚洲第一永久AV网站久久精品男人的天堂AV
|
99精品久久精品一区二区
|
久久婷婷五月综合色奶水99啪
|
亚洲综合日韩久久成人AV
|
欧美性猛交xxxx免费看久久久
|
品成人欧美大片久久国产欧美...
|