[BZOJ 3831]Little Bird

单调队列水体……然而我这蒟蒻仍然WA一墙

这个题本质是一个动态规划,然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……

优先级直接按照递推值来搞即可,递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响,也不过是1,这样撑死也不会使答案更差

但凡是单调队列的题,都会有神秘细节,这题也不例外……顺便说一下这题不要傻乎乎的用pair

代码:

/**************************************************************
    Problem: 3831
    User: danihao123
    Language: C++
    Result: Accepted
    Time:11596 ms
    Memory:16228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=1e6+1;
int D[maxn],f[maxn];
bool d_cmp(int x,int y){
    if(f[x]==f[y])
        return D[x]<D[y];
    else
        return f[x]>f[y];
}
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && d_cmp(D.back(),x))
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
DQueue hhh;
int main(){
    register int i,temp,ans;
    int n,Q,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&D[i]);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&k);
        hhh.push(1);
        f[1]=0;
        for(i=2;i<=n;i++){
            while(hhh.size()>k)
                hhh.pop();
            temp=hhh.top();
            f[i]=f[temp]+(D[temp]<=D[i]);
            hhh.push(i);
        }
        printf("%d\n",f[n]);
        hhh.clear();
    }
    return 0;
}

[洛谷 P2679]子串

DP神题……

第一眼都能看出来是DP,然后大约构思就出来了,但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态,但是注意[tex]A[i]=B[j][/tex](字符数组细节此处未予考虑)的情况和整体情况要独立对待,否则这题只能233

然后下面就不难想了。但是注意直接开数组会233,要开滚动数组防MLE。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}

[CodeVS 1380]没有上司的舞会

树形DP处女作……

刚开始各种蜜汁错误……后来发现dp函数竟然忘写返回值……so sad

代码:

#include <cstdio>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
const int maxn=6001;
vector<int> G[maxn];
void Add_Edge(int x,int y){
	G[x].push_back(y);
}

int d[maxn][2],R[maxn];
int dp(int x,int y,int fa){
	if(d[x][y]!=-0x5ffffff)
		return d[x][y];
	int i,temp;
	if(y==1){
		d[x][y]=R[x];
		for(i=0;i<G[x].size();i++){
			temp=G[x][i];
			if(temp!=fa)
				d[x][y]+=dp(temp,0,x);
		}
	}else{
		d[x][y]=0;
		for(i=0;i<G[x].size();i++){
			temp=G[x][i];
			if(temp!=fa)
				d[x][y]+=max(dp(temp,0,x),dp(temp,1,x));
		}
	}
	return d[x][y];
}

int main(){
	int n,u,v;
	register int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&R[i]);
	for(i=1;i<=n-1;i++){
		scanf("%d%d",&u,&v);
		Add_Edge(u,v);
		Add_Edge(v,u);
	}
	for(i=0;i<=n;i++)
		d[i][0]=d[i][1]=-0x5ffffff;
	printf("%d\n",max(dp(1,0,0),dp(1,1,0)));
	return 0;
}

[BZOJ 2442]修剪草坪

单调队列优化DP……

bi了doge了……现在才能学会一些简单的单调队列优化DP

代码:

继续阅读