[[problem:FENCE]]
FENCE 문제를 푸는데 책과 풀이가 다르게 풀고 있습니다.
제풀이는 처음에 판자데이터를 중복없이 뽑아 냅니다.
뽑아낸 데이터를 오름차순으로 정렬합니다.
정렬된 데이터를 차례대로 뽑습니다.
그래서 구간을 정합니다.
예제데이터 7
7 1 5 9 6 7 3
여기서 가장 작은 판자는 1입니다.
가장작기때문에 모든판자를 다 자를수 있습니다.
그래서 1*7 이되고 다음 작은 판자는 3입니다.
3은 7하나를 자르고 5 9 6 7 3을 자를 수있습니다. 여기서 넓이가 3인 직사각형과 3*5 15인 직사각형이 나옵니다. 여기서 구간이 나누어져서 7과 5 9 6 7 3 으로 나우어지고 다음 판자인 높이 5가 선택되어 구간을 나우어나가 최대값을 저장해 나갑니다.
제가 데이터를 많이 넣어보고 확인 하였으나 오답으로 뜹니다.
오랜시간동안 고민 하였음에도 풀리지않아 답답한 마음에 질문합니다.
고수님들 도와주세여~~~^{^}

#include <cstdio>
bool check[11001];
long n;
long data[21001];
long sawed[11001],cnt;
long ans;
FILE *op;
void set()
{
    int i;
    for(i=1;i<=10000;i++)
    {
        check[i]=false;
    }
    cnt=0;
    ans=-1;
}
void input()
{
    int i;

    scanf("%ld",&n);
    for(i=0;i<n;i++)
    {
        scanf("%ld",&data[i]);
        if(!check[data[i]])
        {
            check[data[i]]=true;
            sawed[cnt++]=data[i];
        }
    }
}
void makeans(long i,long f,long indexOfsawing)
{
    long area;
    area=sawed[indexOfsawing]*(i-f);
    if(area>ans)ans=area;
}
void process(long s,long e,long indexOfsawing)
{
    long i,f=s;
    if(indexOfsawing==cnt)return;
    if(s>e)return;
    if(ans>=sawed[cnt-1]*(e-s+1))return;
    for(i=s;i<=e;i++)
    {
        if(sawed[indexOfsawing]>data[i])
        {
            makeans(i,f,indexOfsawing);
            process(f,i-1,indexOfsawing+1);
            f=i+1;
        }
        else if(i==e)
        {
            makeans(e+1,f,indexOfsawing);
            process(f,e,indexOfsawing+1);
        }
    }


}
void qsort(long a[],long n)
{
    long p,t;
    long i,j;
    if(n>1)
    {
        p=a[n-1];
        i=-1;
        j=n-1;
        while(1)
        {
            while(a[++i]<p);
            while(a[--j]>p);
            if(i>=j)break;
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
        t=a[i];
        a[i]=a[n-1];
        a[n-1]=t;
        qsort(a,i);
        qsort(a+i+1,n-i-1);
    }

}
int main()
{
    int C;
    scanf("%d",&C);
    while(C--)
    {
        set();
        input();
        qsort(sawed,cnt);
        ans=(sawed[0]*n);
        process(0,n-1,1);
        printf("%ld\n",ans);
    }
    return 0;
}