BZOJ 4531: [Bjoi2014]路径

Description

一个无向图,每个节点有一个字符,问形成长度为k的的合法表达式的方案数.

Sol

DP.

\(f[i][o][p][0/1]\) 表示走 \(i\) 步,到 \(o\) ,有 \(p\) 个左括号没有匹配,是否有前导 \(0\) .

分类讨论+大力转移就可以了.

判断好多啊...写挂了好几次...原因就是 \(o\) 打成 \(i\) ...

几个判断我写出来吧...

'-' 前只能为 '0' '1' '2' '3' '4' '5' '6' '7' '8' '9'  '(' ')'

'+' '*' '/'  前只能为 '0' '1' '2' '3' '4' '5' '6' '7' '8' '9' ')'

'(' 前只能为 '-' '+' '*' '/'  '('

')' 前只能为 '0' '1' '2' '3' '4' '5' '6' '7' '8' '9' ')'

'0' 前只能为 '1' '2' '3' '4' '5' '6' '7' '8' '9' '-' '+' '*' '/' '('

'1' '2' '3' '4' '5' '6' '7' '8' '9' 前只能为 '1' '2' '3' '4' '5' '6' '7' '8' '9' '-' '+' '*' '/' '('

Code

/**************************************************************

    Problem: 4531

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:32 ms

    Memory:1716 kb

****************************************************************/

#include<cstdio>

#include<iostream>

using namespace std;

#define debug(a) cout<<#a<<"="<<a<<" "

typedef long long LL;

const int N = 22;

const int K = 35;

const LL Mo = 1000000007;

int n,m,k;LL ans;

char c[N];

int a[N],g[N][N];

LL f[K][N][K][2];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

int main(){

//  freopen("in.in","r",stdin);

//  freopen("out.out","w",stdout);

    n=in(),m=in(),k=in();

    scanf("%s",c+1);

    for(int i=1;i<=n;i++){

        if(c[i]=='-') a[i]=10;

        else if((c[i]>'9'||c[i]<'0')&&c[i]!='('&&c[i]!=')') a[i]=11;

        else if(c[i]=='(') a[i]=12;

        else if(c[i]==')') a[i]=13;

        else a[i]=c[i]-'0';

    }

    for(int i=1,u,v;i<=m;i++) u=in(),v=in(),g[u][v]=g[v][u]=1;

    for(int i=1;i<=n;i++) f[1][i][(a[i]==12)][(a[i]==0)]=(a[i]!=11&&a[i]!=13)?1:0;

//  for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;

//  for(int i=1;i<=n;i++){

//      debug(f[1][i][0][0]),debug(f[1][i][0][1]),debug(f[1][i][1][0]),debug(f[1][i][1][1])<<endl;

//  }

    for(int i=2;i<=k;i++){

        for(int o=1;o<=n;o++){

            for(int j=1;j<=n;j++){

                if(!g[o][j]||o==j) continue;

                for(int p=0;p<=i;p++)

                switch(a[o]){

                    case 10://'-'

                        if(a[j]!=11&&a[j]!=10) f[i][o][p][0]=((f[i][o][p][0]+f[i-1][j][p][0])%Mo+f[i-1][j][p][1])%Mo;

                        break;//0 1 ( )

                    case 11://'+''*''/'

                        if(a[j]<10||a[j]==13) f[i][o][p][0]=((f[i][o][p][0]+f[i-1][j][p][0])%Mo+f[i-1][j][p][1])%Mo;

                        break;//0 1 )

                    case 12://'('

                        if(a[j]>9&&a[j]!=13&&p>0) f[i][o][p][0]=(f[i][o][p][0]+f[i-1][j][p-1][0])%Mo;

                        break;//- + (

                    case 13://')'

                        if(a[j]<10||a[j]==13) f[i][o][p][0]=((f[i][o][p][0]+f[i-1][j][p+1][0])%Mo+f[i-1][j][p+1][1])%Mo;

                        break;//0 1 )

                    default://num

                        if(a[o]==0){//1 - + (

                            if(a[j]<10) f[i][o][p][0]=(f[i][o][p][0]+f[i-1][j][p][0])%Mo;

                            else if(a[j]!=13) f[i][o][p][1]=(f[i][o][p][1]+f[i-1][j][p][0])%Mo;

                        }else{//1 - + (

                            if(a[j]!=13) f[i][o][p][0]=(f[i][o][p][0]+f[i-1][j][p][0])%Mo;

                        }break;

                }

            }

        }

    }

    for(int i=1;i<=n;i++) if(a[i]<10||a[i]==13) ans=(ans+f[k][i][0][0]+f[k][i][0][1])%Mo;

//  for(int i=1;i<=n;i++) debug(f[k].[i][0][0]),debug(f[k][i][0][1])<<endl;

    cout<<ans<<endl;

    return 0;

}