BZOJ 4742 DP

思路：

Claris大大说了

排序以后这个可以看成是括号序列

f[i][j][k]表示到了i j个左括号 k个右括号

                    (f[i][j][k]+=f[i-1][j][k])%=p;

                    if(node[i].id)(f[i][j][k+1]+=f[i-1][j][k])%=p;

                    else (f[i][j+1][k]+=f[i-1][j][k])%=p;

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

int n,m,K,a[],b[],f[][][],top,p=;

struct Node{int wei,id;Node(){}Node(int x,int y){wei=x,id=y;}}node[];

bool cmp(Node x,Node y){if(x.wei!=y.wei)return x.wei<y.wei;return x.id>y.id;}

int main(){

    scanf("%d%d%d",&n,&m,&K);

    for(int i=;i<=n;i++)scanf("%d",&a[i]),node[++top]=Node(a[i],);//FJ

    for(int i=;i<=m;i++)scanf("%d",&b[i]),node[++top]=Node(b[i],);//FP

    sort(node+,node++top,cmp);

    f[][][]=;

    for(int i=;i<=top;i++)

        for(int j=;j<=K;j++)

            for(int k=;k<=K;k++)

                if(j>=k){

                    (f[i][j][k]+=f[i-][j][k])%=p;

                    if(node[i].id)(f[i][j][k+]+=f[i-][j][k])%=p;

                    else (f[i][j+][k]+=f[i-][j][k])%=p;

                }

    printf("%d\n",f[top][K][K]);

}

巴特西

BZOJ 4742 DP

最新文章

热门文章