首页 > 代码库 > hdu1506 dp
hdu1506 dp
1 //Accepted 1428 KB 62 ms 2 // 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 100005; 8 int l[imax_n]; 9 int r[imax_n];10 int a[imax_n];11 int n;12 void Dp()13 {14 l[1]=1;15 a[0]=-1;16 for (int i=2;i<=n;i++)17 {18 int t=i;19 while (a[i]<=a[t-1])20 {21 t=l[t-1];22 }23 l[i]=t;24 }25 r[n]=n;26 a[n+1]=-1;27 for (int i=n-1;i>=1;i--)28 {29 int t=i;30 while (a[i]<=a[t+1])31 {32 t=r[t+1];33 }34 r[i]=t;35 }36 __int64 ans=0;37 for (int i=1;i<=n;i++)38 {39 if ((__int64 )a[i]*(r[i]-l[i]+1)>ans)40 ans=(__int64 )a[i]*(r[i]-l[i]+1);41 }42 printf("%I64d\n",ans);43 }44 int main()45 {46 while (scanf("%d",&n),n)47 {48 for (int i=1;i<=n;i++)49 scanf("%d",&a[i]);50 Dp();51 }52 return 0;53 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。