bzoj1566: [NOI2009]管道取珠 DP

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1566

思路

n个球，第i个球颜色为ai，对于颜色j，对答案的贡献为颜色为j的球的个数的平方
k^2=(1+1+1+..+1)*(1+1++1+..+1)
for (i=1; i<=n; i++) for (j=1; j<=n; j++) if (a[i]==a[j]) ans++;
感觉看起来还是有一丝丝领悟的
转化为两个人分别同时做游戏
取出相同的方案
\(f[i][a][b]\)表示第i轮一个人上面去了a个，第二个上面取了b个
下面的可以算出来
就可以dp了
难在转化上，转移还蛮简单的

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1007,mod=1024523;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,f[2][N][N];
char a[N],b[N];
inline int add(int a) {return a>=mod?a-mod:a;}
int main() {
    // freopen("1.in","r",stdin);
    n=read(),m=read();
    scanf("%s%s",a+1,b+1);
    f[0][0][0]=1;
    int cnt=1;
    for(int k=1;k<=n+m;++k,cnt^=1) { // 第i轮
        for(int i=0;i<=min(n,k);++i) { // 第一人 的 上面已经使用过的珠子的个数
            int j=k-i;// 第一人 的 下面已经使用过的珠子的个数
            for(int x=0;x<=min(n,k);++x) { //第二人 的 上面已经使用过的珠子的个数
                int y=k-x;//第二人 的 下面已经使用过的珠子的个数
                f[cnt][i][x]=0;
                if(a[i]==a[x]&&i-1>=0&&x-1>=0)
                    f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i-1][x-1]);
                if(b[j]==b[y])
                    f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i][x]);
                if(a[i]==b[y]&&i-1>=0)
                    f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i-1][x]);
                if(b[j]==a[x]&&x-1>=0)
                    f[cnt][i][x]=add(f[cnt][i][x]+f[cnt^1][i][x-1]);
            }
        }
    }
    // for(int i=1;i<=n+m;++i) {
    //  cout<<i<<"\n";
    //  for(int j=1;j<=i;++j) {
    //      for(int k=1;k<=i;++k) {
    //          cout<<f[i][j][k]<<" ";
    //      }
    //      cout<<"\n";
    //  }
    //  puts("");
    // }
    printf("%d\n",f[cnt^1][n][n]);
    return 0;
}