NOI 2009 管道取珠 90 -＞ 100

传送门：https://www.luogu.com.cn/problem/P1758

90分：

#include<cstdio>
#include<iostream>
#define l (i + j - k)
using namespace std;
const int mod = 1024523;
int n, m;
int f[2][507][507];
char a[1007], b[1007];
int d;
inline void add(register int a, register int & b) {
b += a;
if(b >= mod)b -= mod;
}
signed main() {
scanf("%d %d", &n, &m);
scanf("%s", a + 1);
scanf("%s", b + 1);
f[0][0][0] = 1;
for(register int i = 0; i <= n; ++i) {
for(register int j = 0; j <= m; ++j) {
for(register int k = 0; k <= n; ++k) {
if(l > m || l < 0)continue;
if(a[i + 1] == a[k + 1])add(f[d][j][k], f[d ^ 1][j][k + 1]);
if(a[i + 1] == b[l + 1])add(f[d][j][k], f[d ^ 1][j][k]);
if(b[j + 1] == a[k + 1])add(f[d][j][k], f[d][j + 1][k + 1]);
if(b[j + 1] == b[l + 1])add(f[d][j][k], f[d][j + 1][k]);
f[d][j][k] = 0;
}
}
d ^= 1;
}
printf("%dn", f[d][m][n]);
return 0;
}

100分：

#include<cstdio>
#include<iostream>
#define l (i + j - k)
using namespace std;
const int mod = 1024523;
int n, m;
int f[2][507][507];
char a[1007], b[1007];
int d;
inline void add(register int a, register int & b) {
b += a;
if(b >= mod)b -= mod;
}
signed main() {
scanf("%d %d", &n, &m);
scanf("%s", a + 1);
scanf("%s", b + 1);
f[0][0][0] = 1;
for(register int i = 0; i <= n; ++i) {
for(register int j = 0; j <= m; ++j) {
for(register int k = 0; k <= n; ++k) {
if(l > m || l < 0)continue;
if(!f[d][j][k])continue; //这句话让代码快了5倍不止
if(a[i + 1] == a[k + 1])add(f[d][j][k], f[d ^ 1][j][k + 1]);
if(a[i + 1] == b[l + 1])add(f[d][j][k], f[d ^ 1][j][k]);
if(b[j + 1] == a[k + 1])add(f[d][j][k], f[d][j + 1][k + 1]);
if(b[j + 1] == b[l + 1])add(f[d][j][k], f[d][j + 1][k]);
f[d][j][k] = 0;
}
}
d ^= 1;
}
printf("%dn", f[d][m][n]);
return 0;
}

最后

以上就是失眠冬天为你收集整理的NOI 2009 管道取珠 90 -＞ 100的全部内容，希望文章能够帮你解决NOI 2009 管道取珠 90 -＞ 100所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。