常用技巧（二）

栈

POJ 3250: Bad Hair Day
题意：统计每个数字右边第一个比它大的数字与它的下标差的和。
单调栈模板题。（相当于只从一头进出的单调严格递减栈）
然后反过来思考，统计每头牛被多少头牛看到，作为这头牛对答案的贡献即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题意：统计每个数字右边第一个比它大的数字与它的下标差的和。
单调栈模板题。（相当于只从一头进出的单调严格递减栈） 
然后反过来思考，统计每头牛被多少头牛看到，作为这头牛对答案的贡献即可。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=80000+5;
const int INF=0x3f3f3f3f;
int q[maxn],n,h[maxn];
ll ans=0ll;
void solve(){
    int head=1,tail=1;
    q[head]=1;
    for(int i=2;i<=n+1;i++){
        while(head<=tail&&h[q[tail]]<=h[i]) tail--;
        ans+=(ll)(tail-head+1); //此时栈中的元素都能看到i 即i的贡献就是栈中元素的数量tail-head+1 
        q[++tail]=i;
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Bad Hair Day.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    h[n+1]=INF;
    solve();
    printf("%lld",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 2082: Terrible Sets
预处理出l[i]和r[i]为i号矩形向左/右能够达到的最远小标距离，可以用两个严格单调增的单调栈实现。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
预处理出l[i]和r[i]为i号矩形向左/右能够达到的最远小标距离，可以用两个严格单调增的单调栈实现。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
int w[maxn],h[maxn],n;
int ans;
int q[maxn],l[maxn],r[maxn];
void init(){
    ans=0;
}
void solve(){
    int head=1,tail=1;
    q[head]=0;
    h[0]=-INF;
    for(int i=1;i<=n;i++){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        l[i]=w[i]-w[q[tail]];
        q[++tail]=i;
    }
//  for(int i=1;i<=n;i++) D(l[i]);
//  E;
    head=1,tail=1;
    q[head]=n+1;
    h[n+1]=-INF;
    for(int i=n;i>=1;i--){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        r[i]=w[q[tail]-1]-w[i-1];
        q[++tail]=i;
    }
//  for(int i=1;i<=n;i++) D(r[i]);
//  E;
    for(int i=1;i<=n;i++) ans=max((l[i]+r[i]-w[i]+w[i-1])*h[i],ans);
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Terrible Sets.in","r",stdin);
    while(scanf("%d",&n)){
        if(n==-1) break;
        init();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&w[i],&h[i]);
            w[i]+=w[i-1];
        }
        solve();
        printf("%d\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3494: Largest Submatrix of All 1’s
悬线法裸题，不再赘述。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
悬线法裸题，不再赘述。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int INF=0x3f3f3f3f;
int n,m,a[maxn][maxn],q[maxn],h[maxn],l[maxn],r[maxn],ans;
void init(){
    ans=0;
}
int calc(){ //计算h[i]表示的最大矩形 
    int res=0;
//  for(int i=1;i<=m;i++) D(h[i]);
//  E;
    int head=1,tail=1;
    q[head]=0;
    h[0]=-INF;
    for(int i=1;i<=m;i++){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        l[i]=i-q[tail];
        q[++tail]=i;
    }
//  for(int i=1;i<=m;i++) D(l[i]);
//  E;
    head=1,tail=1;
    q[head]=m+1;
    h[m+1]=-INF;
    for(int i=m;i>=1;i--){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        r[i]=q[tail]-i;
        q[++tail]=i;
    }
//  for(int i=1;i<=m;i++) D(r[i]);
//  E;
    for(int i=1;i<=m;i++) res=max((l[i]+r[i]-1)*h[i],res);
    return res;
}
void solve(){
    for(int i=1;i<=n;i++){
        memcpy(h,a[i],sizeof(a[i]));
        ans=max(calc(),ans);
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Largest Submatrix of All 1’s.in","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF) {
        init(); 
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {
                scanf("%d",&a[i][j]);
                if(a[i][j]!=0) a[i][j]+=a[i-1][j];
            }
        /*
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                cout<<a[i][j]<<" ";
            }
            E;
        }
        */
        solve();
        printf("%d\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

双端队列

POJ 2823: Sliding Window
单调队列模板题，不再赘述。
注意k=1的情况。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
单调队列模板题，不再赘述。
注意k=1的情况。  
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e6+5;
const int INF=0x3f3f3f3f;
int n,k,a[maxn];
int q[maxn];
int mn[maxn],mx[maxn]; //最小值 最大值 
void solve(){
    int head=1,tail=1;
    q[head]=1;
    mn[1]=mx[1]=a[1]; //注意k=1的情况 
    //1 3 -1 -3 5 3 6 7
    for(int i=2;i<=n;i++){
        while(head<=tail&&i-q[head]+1>k) head++; //i-q[head]+1为单调队列中的元素数量 
        while(head<=tail&&a[i]<=a[q[tail]]) tail--;
        q[++tail]=i;
//      for(int j=head;j<=tail;j++) D(a[q[j]]);
//      E;
        mn[i]=a[q[head]];
    }
    head=1,tail=1;
    q[head]=1;
    for(int i=2;i<=n;i++){
        while(head<=tail&&i-q[head]+1>k) head++; 
        while(head<=tail&&a[i]>=a[q[tail]]) tail--;
        q[++tail]=i;
//      for(int j=head;j<=tail;j++) D(a[q[j]]);
//      E;
        mx[i]=a[q[head]];
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Sliding Window.in","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    solve();
    for(int i=k;i<=n;i++) printf("%d ",mn[i]);
    printf("\n");
    for(int i=k;i<=n;i++) printf("%d ",mx[i]);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3260: The Fewest Coins
题解链接 https://blog.csdn.net/u013480600/article/details/40617083
以为需要单调队列来优化多重背包的，结果竟然直接过了。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 https://blog.csdn.net/u013480600/article/details/40617083
以为需要单调队列来优化多重背包的，结果竟然直接过了。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=10000+120*120+5; //maxt+maxv*maxv
const int INF=0x3f3f3f3f;
int n,t,v[maxn],c[maxn];
int m,maxv=0,ans=INF;
int d[maxm],f[maxm]; //d 支付 f 找零 
void init(){
    memset(f,INF,sizeof(f));
    memset(d,INF,sizeof(d));
    f[0]=d[0]=0;
}
void dp1(){
    for(int i=1;i<=n;i++){
        if(v[i]*c[i]>=m) for(int j=v[i];j<=m;j++) d[j]=min(d[j],d[j-v[i]]+1);
        else{
            for(int j=m;j>=v[i];j--) for(int k=1;k<=c[i]&&j-k*v[i]>=0;k++) d[j]=min(d[j],d[j-k*v[i]]+k);
        }
    }
}
void dp2(){
    for(int i=1;i<=n;i++) for(int j=v[i];j<=m;j++) f[j]=min(f[j],f[j-v[i]]+1);
}
void solve(){
    for(int i=t;i<=m;i++) ans=min(ans,d[i]+f[i-t]);
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("The Fewest Coins.in","r",stdin);
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d",&v[i]),maxv=max(maxv,v[i]);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    m=t+maxv*maxv;
    init();
    dp1();
    dp2();
    solve();
    if(ans==INF) printf("-1");
    else printf("%d",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 1180: Batch Scheduling
题解链接 //www.greatytc.com/p/fdb41c13d11f
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 //www.greatytc.com/p/fdb41c13d11f 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int INF=0x3f3f3f3f;
int n,s,t[maxn],c[maxn];
int q[maxn],f[maxn];
void solve(){
    int l=1,r=1;
    f[0]=0;
    q[l]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&(s+t[i])*(c[q[l+1]]-c[q[l]])>=f[q[l+1]]-f[q[l]]) l++;
        f[i]=f[q[l]]-(s+t[i])*c[q[l]]+t[i]*c[i]+s*c[n];//要使f[i]最小 就要f[j]最小 在截距一定的情况下 队首的斜率最小 所以结构也最小 
        while(l<r&&(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])) r--;
        q[++r]=i;
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Batch Scheduling.in","r",stdin);
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++) scanf("%d%d",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
    solve();
    printf("%d",f[n]);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,546评论 6赞 507
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,224评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,911评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,737评论 1赞 294
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,753评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,598评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,338评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,249评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,696评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,888评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,013评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,731评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,348评论 3赞 330
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,929评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,048评论 1赞 270
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,203评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,960评论 2赞 355

常用技巧（二）

栈

双端队列

推荐阅读更多精彩内容