当前位置： 移动技术网 > IT编程>开发语言>C/C++ > [NOI2009] 管道取珠

[NOI2009] 管道取珠

2019年01月04日  | 移动技术网IT编程  | 我要评论

2012年的快乐大本营,怀仁一中招聘,517云购

题有点骚。。

sum a[i]*a[i]可以理解为两个独立但同时进行的游戏得到同一个输出序列的方案数。

设f[l,i,j]为每个游戏都已经推出了l个珠子时，第一个游戏里上边儿的管道已经推出了i个，第二个游戏中上边儿管道推出了j个的方案数。

考虑到若要推出序列相同，那么对于每个阶段l，两个游戏的推出序列应始终相等。这样，跑跑计数dp就好了

#include <bits/stdc++.h>
using namespace std;
const int n=507;
const int p=1024523;

int n,m;
char a[n],b[n];
int f[2][n][n];

inline void add(int&x,int y) {
    if((x+=y)>=p) x-=p;
}

int main() {
    scanf("%d%d%s%s",&n,&m,a+1,b+1);
    f[0][0][0]=1;
    int now=0, nxt=1;
    for(int l=0; l<n+m; ++l) {
        for(int i=0; i<=l && i<=n; ++i) {
            for(int j=0; j<=l && j<=n; ++j) {
                if(!f[now][i][j]) continue;
                if(a[i+1]==a[j+1]) add(f[nxt][i+1][j+1],f[now][i][j]);
                if(a[i+1]==b[l-j+1]) add(f[nxt][i+1][j],f[now][i][j]);
                if(b[l-i+1]==a[j+1]) add(f[nxt][i][j+1],f[now][i][j]);
                if(b[l-i+1]==b[l-j+1]) add(f[nxt][i][j],f[now][i][j]);
                f[now][i][j]=0;
            }
        }
        now=nxt, nxt^=1;
    }
    printf("%d\n",f[now][n][n]);
}

算是可做题吧。。。

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网