hdu 1506 Largest Rectangle in a Histogram(求最大的矩形)

hdu 1506 Largest Rectangle in a Histogram(求最大的矩形)

1.注意要把a[]定義為LL，我在這裡wa了N次

2.尋找邊界時，得用dp思想

AC代碼：

#include
#include
#define LL long long
using namespace std;

const LL INF=1<<60;
LL a[100005];//要定義為LL
int L[100005];
int R[100005];

int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=n;i++)//用dp思想，不斷地擴展邊界
        {
            L[i]=i;
            while(L[i]>1&&a[L[i]-1]>=a[i])
                L[i]=L[L[i]-1];
        }
        for(int i=n;i>=1;i--)
        {
            R[i]=i;
            while(R[i]=a[i])
                R[i]=R[R[i]+1];
        }
        LL ans=-INF;
        for(int i=1;i<=n;i++)
        {
            LL temp=a[i]*(R[i]-L[i]+1);
            if(ans沒用dp思想找邊界的超時代碼：
 
 
#include
#include
#define LL long long
using namespace std;

const LL INF=1<<60;
LL a[100005];
int L[100005];
int R[100005];

int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=n;i++)//超時，得用dp思想優化
        {
            int j=i;
            while(j>1&&a[j]>=a[i])
                j--;
            L[i]=++j;
        }
        for(int i=1;i<=n;i++)
        {
            int j=i;
            while(j=a[i])
                j++;
            R[i]=--j;
        }
        LL ans=-INF;
        for(int i=1;i<=n;i++)
        {
            LL temp=a[i]*(R[i]-L[i]+1);
            if(ans