昨天ACdream群里在讨论单调栈，今天就遇到无数WA，现在也没有没有搞明白单调栈的原理，更没有搞明白我的DP 或者 贪心，怎么不对。
单调栈是个好东西，容我去看看啊！
poj 2559
总结：long long类型，要和int区分开来，输出格式用"%I64d"。
数据结构该看看了。
自己多分析分析。
写完一次就AC了，之前的贪心一直都WA呢。囧……
#include<stdio.h>
#include<string.h>
#include<math.h>
int n,pos[100005];
long long stack[100005];
int main()
{
int i,top;
long long a,ans;
while (scanf("%d",&n)==1&&n)
{
top=0;ans=0;
stack[top]=0;pos[top]=0;
for (i=1 ;i<=n ;i++ )
{
scanf("%I64d",&a);
while (top>0&&a<=stack[top])
{
if (ans<(long long)(i-1-pos[top-1])*stack[top])
ans=(long long)(i-1-pos[top-1])*stack[top];
top--;
}
top++;
stack[top]=a;
pos[top]=i;
}
while (top>0)
{
if (ans<(long long)(n-pos[top-1])*stack[top])
ans=(long long)(n-pos[top-1])*stack[top];
top--;
}
printf("%I64d\n",ans);
}
return 0;
}
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;
}
额，要学的东西还很多啊。