poj 2082
这个题目比较坑爹，简单的问题让他给叙述的深奥无比！ＮＰ！！！！数学理解能力当然重要啊！
搞清题意后，想到的就是ＤＰ了，感觉有个四边形不等式在里面可以用。。。贪心法应该也是正确的啊，不过一直ＷＡ，也不知道怎么回事。该好好研究研究单调栈，单调队列了。。。。呜呜呜匆
ＷＡ了无数次，单调栈一次ＡＣ！
#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;
}