昨天ACdream群里在討論單調(diào)棧，今天就遇到無數(shù)WA，現(xiàn)在也沒有沒有搞明白單調(diào)棧的原理，更沒有搞明白我的DP 或者 貪心，怎么不對。
單調(diào)棧是個好東西，容我去看看啊！
poj 2559
總結(jié)：long long類型，要和int區(qū)分開來，輸出格式用"%I64d"。
數(shù)據(jù)結(jié)構(gòu)該看看了。
自己多分析分析。
寫完一次就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
這個題目比較坑爹，簡單的問題讓他給敘述的深奧無比！ＮＰ！！！！數(shù)學(xué)理解能力當(dāng)然重要啊！
搞清題意后，想到的就是ＤＰ了，感覺有個四邊形不等式在里面可以用。。。貪心法應(yīng)該也是正確的啊，不過一直ＷＡ，也不知道怎么回事。該好好研究研究單調(diào)棧，單調(diào)隊列了。。。。嗚嗚嗚匆
ＷＡ了無數(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;
}
額，要學(xué)的東西還很多啊。