Welcome, Guest! Sign Up RSS

Clever Space

Friday, 11.22.2024
Main » 2013 » August » 21 » 神奇的STL
10:34 AM
神奇的STL
Prob.

1591: [NOIP2010模拟赛]琪露诺

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 34  Solved: 19
[Submit][Status][Web Board]

Description

在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只会移动到i+L到i+R中的一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。每一个格子都有一个冰冻指数A[i]，编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。开始时，琪露诺在编号0的格子上，只要她下一步的位置编号大于N就算到达对岸。

Input

第1行：3个正整数N, L, R 第2行：N+1个整数，第i个数表示编号为i-1的格子的冰冻指数A[i-1]

Output

第1行：一个整数，表示最大冰冻指数。保证不超过2^31-1

Sample Input

5 2 3 0 12 3 11 7 -2

Sample Output

11

HINT

对于60%的数据：N = 10,000
对于100%的数据：N = 200,000
对于所有数据 -1,000 = A[i] = 1,000且1 = L = R = N

Code.

#include<cstdio> #include<cstdlib> #include<set> #define ittype multiset<int>::iterator #define N 200100 using namespace std; multiset<int> dp; int n,L,R,i,tot; int a[N],f[N]; int main() { scanf("%d %d %d",&n,&L,&R); for (i=0;i<=n;i++) scanf("%d",&a[i]); f[0]=0; for (i=1;i<=L-1;i++) f[i]=-100000000; for (i=L;i<=2*n;i++) { if ((i-1-R)>=0) { ittype it=dp.find(f[i-1-R]); dp.erase(it); } dp.insert(f[i-L]); ittype it=dp.end(); it--; int m=*it; f[i]=m+a[i]; } printf("%d\n",f[2*n]); }


Views: 445 | Added by: dhy0077 | Rating: 5.0/1
Total comments: 0
Only registered users can add comments.
[ Sign Up | Login ]