比赛 |
20110928 |
评测结果 |
AAAAWAAAAA |
题目名称 |
交错匹配 |
最终得分 |
90 |
用户昵称 |
Citron酱 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-09-28 20:54:13 |
显示代码纯文本
#include <fstream>
#define I_F "crossa.in"
#define O_F "crossa.out"
const int MAXn=200;
int l[2];
int s[2][MAXn];
int p[2][MAXn][MAXn];
int ans;
void Input();
void Predo();
int Max(const int, const int);
void Dynap();
void Output();
int main()
{
Input();
Predo();
Dynap();
Output();
return 0;
}
void Input()
{
std::ifstream fin(I_F);
fin>>l[0]>>l[1];
for (short i=0; i<2; i++)
for (int j=0; j<l[i]; fin>>s[i][j++]);
fin.close();
}
void Predo()
{
for (short i=0; i<2; i++)
for (int j=0; j<l[i]; j++)
{
p[i][j][0]=(s[i][j]==s[1-i][0])?0:-1;
for (int k=1; k<l[1-i]; k++)
p[i][j][k]=(s[i][j]==s[1-i][k])?k:p[i][j][k-1];
}
}
int Max(const int a, const int b)
{
return (a>b)?a:b;
}
void Dynap()
{
int f[MAXn][MAXn]={0};
for (int i=1; i<l[0]; i++)
for (int j=1; j<l[1]; j++)
if (p[0][i][j]>=0 && p[1][j][i]>=0 && (!(p[0][i][j]==j && p[1][j][i]==i)))
f[i][j]=Max(f[i-1][j],Max(f[i][j-1],((p[0][i][j]*p[1][j][i]>0)?f[p[1][j][i]-1][p[0][i][j]-1]:0)+1));
else
f[i][j]=Max(f[i][j-1],f[i-1][j]);
ans=f[l[0]-1][l[1]-1]*2;
}
void Output()
{
std::ofstream fout(O_F);
fout<<ans<<std::endl;
fout.close();
}