Feel Good (poj 2796)

题目大意就是在给出的串中找出一段连续数字,使得 这一段的和 乘上 这一段最小的数 的结果最大。

可以用rmq做。每次区间找当中最小的数,算出值并记录位置。然后再递推它的左右区间。

不过- -,一开始用深搜递推RE了。栈空间不够了,然后慢慢优化,最后还是ac了。

貌似这一题是用单调栈做的,还可以用查并集做。。。我也是醉了

具体看代码吧

 1 /*************************************************************************
 2     > File Name: c.cpp
 3     > Author: milaso
 4     > Mail: [email protected]
 5     > Created Time: 2014年07月21日 星期一 21时18分40秒
 6  ************************************************************************/
 7 //#pragma comment(linker, "/STACK:1024000000,1024000000")
 8 //如果自己电脑上100000的数据过的了,但是oj RE 那就加上上面的代码
 9 #include<iostream>
10 #include<math.h>
11 #include<algorithm>
12 #include<string.h>
13 #include<string>
14 #include<stdio.h>
15 #include<fstream>
16 using namespace std;
17
18 int num[100010];
19 long long  sum[100010];
20 int pos[100010][17]; // 最好只开17吧,不然可能RE
21 int  n;
22
23 struct node{
24     long long ans;
25     int l,r;
26 };
27
28
29 void rmq_ini(){
30     for(int i=1;i<=n;i++) pos[i][0] =i;
31     for(int j=1;(1<<j) <=n;j++)
32         for(int i=1;(i+(1<<j)-1) <= n;i++ ){
33             if(num[pos[i][j-1]] < num [pos[i+(1<<(j-1))][j-1]]){
34                 pos[i][j] = pos[i][j-1];
35             }
36             else
37                 pos[i][j] = pos[i+(1<<(j-1))][j-1];
38         }
39 }
40
41 int rmq(int l,int r){
42     int k=0;
43     while((2<<k) <=(r-l+1)) k++;
44     if(num[pos[l][k]] < num[pos[r-(1<<k)+1][k]])
45         return pos[l][k];
46     else
47         return pos[r-(1<<k)+1][k];
48 }
49
50
51 node dfs(int l,int r){ // !!!!!!!!!最好只用两个node,不然会RE
52     node a;
53     if( l == r) {
54         a.ans=0;
55         a.l = l;
56         a.r = r;
57         return a;
58     }
59     if (l+1 == r){
60         a.ans=(long long )num[r]* (long long )num[r];
61         a.l = l;
62         a.r = r;
63         return a;
64     }
65     int m=rmq(l+1,r);
66     node an;
67     an.ans=(sum[r]-sum[l])*num[m];an.l=l;an.r=r;
68     a = dfs(l,m-1);
69     if(a.ans > an.ans){
70         an.ans= a.ans;
71         an.l=a.l;an.r=a.r;
72     }
73     a =dfs(m,r);
74     if(a.ans > an.ans){
75         an.ans =a.ans;
76         an.l=a.l;an.r=a.r;
77     }
78     return an;
79 }
80
81
82
83 int main(){
84     scanf("%d",&n);
85     for(int i=1;i<=n;i++){
86         scanf("%d",&num[i]);
87         sum[i] = sum[i-1] + num[i];
88     }
89     rmq_ini();
90     node ans=dfs(0,n);
91     //long long  ans=dfs(0,n);
92     //cout<<ans<<endl;
93     cout<<ans.ans<<endl<<ans.l + 1<<" "<<ans.r<<endl; //l要加一哦
94     return 0;
95 }

Feel Good (poj 2796)

时间: 07-22

Feel Good (poj 2796)的相关文章

HDU 1325 Is It A Tree? (POJ 1308)

并查集问题... 这题以前做过-- 以前做过-- 做过-- 过-- 不过重做时候被吭得异常之爽-- 在判断 vis[i]的时候.我记得标准C++是非0 即为真. 而我用C++ 提交的时候 if(vis[i]) 去直接给我WA了. 用G++ 就AC了...然后改成if(vis[i]==1) 交C++ 就AC了. 特瞄的我每次初始化都把 vis[i] 都赋值为 0 了..都能出这种错? 求路过大神明示我的错误. 题意是判断是否是一棵树. 不能存在森林,用并查集合并,每个点的入度不能超过1. 比如 1

HDU 1535 Invitation Cards (POJ 1511)

两次SPFA.求 来 和 回 的最短路之和. 用Dijkstra+邻接矩阵确实好写+方便交换,但是这个有1000000个点,矩阵开不了. d1[]为 1~N 的最短路. 将所有边的 邻点 交换. d2[] 为 1~N 的最短路. 所有相加为 所要答案. 忧伤的是用SPFA  "HDU 1535"  AC了,但是POJ 一样的题 "POJ 1511" 就WA了. 然后强迫症犯了,不停的去测试. 题意中找到一句关键话 :Prices are positive integ

每日一dp(1)——Largest Rectangle in a Histogram(poj 2559)使用单调队列优化

Largest Rectangle in a Histogram 题目大意: 有数个宽为1,长不定的连续方格,求构成的矩形中最大面积 /************************************************************************/ /* 思路1. 当前为n的面积如何与n-1相联系,dp[i][j]=max(dp[i-1][k]) , 0<k<=j 描述:i为方块个数,j为高度 但是此题目的数据对于高度太变态,h,1000000000 ,n,1

Power string(poj 2406)

题目大意,给出一个字符串s,求最大的k,使得s能表示成a^k的形式,如 abab 可以表示成(ab)^2: 方法:首先 先求kmp算法求出next数组:如果 len mod (len-next[len])==0 ,答案就是 len /(len-next[len]),否则答案是1:证明如下: 如果s能表示成 a^k的形式且k>1,k尽可能大,即s可以表示成aaaaaa(k个a):那么next[len]就等于k-1个a的长度:aaaaaaa  aaaaaaa那么 (len-next[len])a的长

(多重背包+记录路径)Charlie&#39;s Change (poj 1787)

http://poj.org/problem?id=1787 描述 Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at coffee vending machines at motorests. Charlie hates change. That is basically the setup of your next task. Your

昂贵的聘礼(poj 1062)

Description 年轻的探险家来到了一个印第安部落里.在那里他和酋长的女儿相爱了,于是便向酋长去求亲.酋长要他用10000个金币作为聘礼才答应把女儿嫁给他.探险家拿不出这么多金币,便请求酋长降低要求.酋长说:"嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币.如果你能够弄来他的水晶球,那么只要5000金币就行了."探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格.探险家于是又跑到其他地方,其他人也提出了类似的要求

Collecting Bugs(POJ 2096)

Collecting Bugs Time Limit: 10000MS   Memory Limit: 64000K Total Submissions: 3064   Accepted: 1505 Case Time Limit: 2000MS   Special Judge Description Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material s

Games:取石子游戏(POJ 1067)

取石子游戏 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 37662   Accepted: 12594 Description 有两堆石子,数量任意,可以不同.游戏开始由两个人轮流取石子.游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子:二是可以在两堆中同时取走相同数量的石子.最后把石子全部取完者为胜者.现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者

Machine Schedule(poj 1325)

Description As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of sch