首页 > 代码库 > 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 }
View Code