首页 > 代码库 > hdu--1506--矩阵求和<stack>
hdu--1506--矩阵求和<stack>
草噢 先发泄一下 一个写错 TM地 找了我半小时多的错误 擦
真SB。。。
一把游戏时间。。。
先放题目上来 touch me
这题 是上一题的简单版=-= 上一题掌握了 这题 很简单
被这个 找错给折磨了 不想多讲了
这个stack的写法 难想到 但是容易看懂 不清楚的 留言 给我 =-= 缺人互动 好寂寞。。。
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 typedef long long LL; 6 const int size = 100010; 7 int Left[size]; 8 int Right[size]; 9 LL h[size];10 11 int main()12 {13 int i , n;14 LL ans , area;15 while( cin >> n && n )16 {17 ans = 0;18 h[0] = h[n+1] = -1;19 for( i = 1 ; i<=n ; i++ )20 {21 cin >> h[i];22 Left[i] = Right[i] = i;23 }24 for( i = 2 ; i<=n ; i++ )25 {26 while( h[ Left[i]-1 ] >= h[i] )27 {28 Left[i] = Left[ Left[i]-1 ];29 }30 }31 for( i = n-1 ; i>=1 ; i-- )32 {33 while( h[ Right[i]+1 ] >= h[i] )34 {35 Right[i] = Right[ Right[i]+1 ];36 }37 }38 for( i = 1 ; i<=n ; i++ )39 {40 area = (LL) h[i] * ( Right[i] - Left[i] + 1 );41 ans = max( ans , area );42 } 43 cout << ans << endl;44 }45 return 0;46 }
1 #include <iostream> 2 #include <stack> 3 #include <algorithm> 4 using namespace std; 5 6 typedef long long LL; 7 const int size = 100010; 8 LL h[size]; 9 struct data10 {11 int w;12 LL h;13 data( int x , LL y )14 {15 w = x;16 h = y;17 }18 };19 stack<data>s;20 21 int main()22 {23 cin.sync_with_stdio(false);24 int n , totalW;25 LL area , ans;26 while( cin >> n && n )27 {28 for( int i = 0 ; i<n ; i++ )29 {30 cin >> h[i];31 }32 ans = h[n] = 0;33 while( !s.empty() )34 s.pop();35 for( int i = 0 ; i<=n ; i++ )36 {37 if( s.empty() || h[i] > s.top().h )38 {39 s.push( data( 1,h[i] ) );40 }41 else if( h[i] == s.top().h )42 {43 s.top().w ++;44 }45 else46 {47 totalW = 0;48 while( !s.empty() && h[i] < s.top().h )49 {50 totalW += s.top().w;51 area = (LL)totalW * s.top().h;52 ans = max( ans , area );53 s.pop();54 }55 s.push( data( totalW+1,h[i] ) );56 }57 }58 cout << ans << endl;59 }60 return 0;61 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。