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
久久精品国产精品亚洲精品
|
久久精品国产精品亚洲毛片
|
中文字幕久久亚洲一区
|
久久99久国产麻精品66
|
亚洲国产精品高清久久久
|
草草久久久无码国产专区
|
伊人情人综合成人久久网小说
|
亚洲精品乱码久久久久久
|
国产成人精品久久一区二区三区av
|
久久久久人妻精品一区三寸蜜桃
|
免费久久人人爽人人爽av
|
青青草国产精品久久久久
|
精品国产乱码久久久久久人妻
|
国产精品激情综合久久
|
国产精品欧美久久久天天影视
|
欧美一区二区久久精品
|
久久精品国产精品亚洲人人
|
亚洲精品乱码久久久久久
|
天天影视色香欲综合久久
|
久久香蕉国产线看观看99
|
久久久久人妻一区精品性色av
|
久久99国产亚洲高清观看首页
|
久久精品aⅴ无码中文字字幕不卡
|
国产精品免费久久
|
久久99毛片免费观看不卡
|
久久精品黄AA片一区二区三区
|
亚洲欧美成人综合久久久
|
欧美日韩精品久久久久
|
一本色道久久综合
|
久久久亚洲裙底偷窥综合
|
国产一区二区久久久
|
中文字幕无码av激情不卡久久
|
久久综合精品国产一区二区三区
|
国内精品久久久久久不卡影院
|
国产成人无码精品久久久久免费
|
国产精品永久久久久久久久久
|
精品久久人人做人人爽综合
|
人妻无码精品久久亚瑟影视
|
久久精品国产亚洲AV忘忧草18
|
日韩精品久久无码人妻中文字幕
|
丁香色欲久久久久久综合网
|