poj 2082
這個(gè)題目比較坑爹，簡(jiǎn)單的問(wèn)題讓他給敘述的深?yuàn)W無(wú)比！ＮＰ！！！！數(shù)學(xué)理解能力當(dāng)然重要啊！
搞清題意后，想到的就是ＤＰ了，感覺(jué)有個(gè)四邊形不等式在里面可以用。。。貪心法應(yīng)該也是正確的啊，不過(guò)一直ＷＡ，也不知道怎么回事。該好好研究研究單調(diào)棧，單調(diào)隊(duì)列了。。。。嗚嗚嗚匆
ＷＡ了無(wú)數(shù)次，單調(diào)棧一次ＡＣ！
#include<stdio.h>
#include<string.h>
#include<math.h>
int n;
long long stack[50005],pos[50005],sum;
long long ans,w,h;
int main()
{
int i,top;
while (scanf("%d",&n)==1&&n!=-1)
{
sum=0;top=0;ans=0;
for (i=1;i<=n ;i++ )
{
scanf("%I64d%I64d",&w,&h);
while (top>0&&h<=stack[top])
{
if (ans<(sum-pos[top-1])*stack[top])
ans=(sum-pos[top-1])*stack[top];
top--;
}
sum+=w;
top++;
stack[top]=h;
pos[top]=sum;
}
while (top>0)
{
if (ans<(sum-pos[top-1])*stack[top])
ans=(sum-pos[top-1])*stack[top];
top--;
}
printf("%I64d\n",ans);
}
return 0;
}