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
閱讀(142)
評論(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亚洲人成电影网站
|
国产成人综合久久久久久
|
亚洲性久久久影院
|
久久国产精品99精品国产987
|
国产精品伊人久久伊人电影
|
伊人久久大香线蕉综合影院首页
|
久久精品人人做人人爽97
|
国产精自产拍久久久久久蜜
|
久久丫精品国产亚洲av不卡
|
99久久精品日本一区二区免费
|
国产亚洲精久久久久久无码AV
|
日韩AV无码久久一区二区
|
精品久久久久久99人妻
|
99精品国产在热久久无毒不卡
|
亚洲国产精品无码久久青草
|
久久精品国产秦先生
|
国内精品伊人久久久久777
|
国产亚洲精午夜久久久久久
|
久久午夜福利电影
|
日本精品久久久久中文字幕8
|
国色天香久久久久久久小说
|
久久嫩草影院免费看夜色
|
亚洲国产精久久久久久久
|
国产亚洲婷婷香蕉久久精品
|
日韩乱码人妻无码中文字幕久久
|
欧美精品乱码99久久蜜桃
|
色综合久久88色综合天天
|
激情久久久久久久久久
|
国产高潮久久免费观看
|
国产午夜福利精品久久
|
国产午夜精品理论片久久
|
国产福利电影一区二区三区久久久久成人精品综合
|
99久久99这里只有免费费精品
|
久久久国产乱子伦精品作者
|
久久久久成人精品无码中文字幕
|
久久精品国产91久久综合麻豆自制
|
久久精品亚洲精品国产色婷
|
久久久亚洲欧洲日产国码二区
|
久久国产高清一区二区三区
|