QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#10184 | #305. 最长公共相似子序列问题 | hanyuwei | 80 | 951ms | 18980kb | C++20 | 1.6kb | 2021-05-06 14:42:03 | 2023-08-25 00:54:10 |
Judging History
answer
//Love and Freedom.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<ctime>
#define ll long long
#define inf 20021225
#define N 2010
#define db double
using namespace std;
int read()
{
int s=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*f;
}
int f[N][N],n,s[N],t[N],val[N]; char a[N],b[N]; bool vis[N];
int get(char c){return c=='A'?1:c=='C'?2:c=='G'?3:4;}
int get(int x)
{
for(int j=1,k=x;j<=n;j++,k++)
{
if(k>n) k=1;
for(int i=1;i<=n;i++)
f[j][i]=max(f[j-1][i-1]+(s[i]==t[k]),max(f[j][i-1],f[j-1][i]));
}
return f[n][n];
}
struct node{int v,x;};
bool operator<(node a,node b){return a.v<b.v;}
priority_queue<node> pos;
int main()
{
//freopen("midnight.in","r",stdin); freopen("midnight.out","w",stdout);
srand(20021225); n=read(); scanf("%s%s",a+1,b+1);
for(int i=1;i<=n;i++) s[i]=get(a[i]),t[i]=get(b[i]);
if(n<=600){int ans=0; for(int i=1;i<=n;i++) ans=max(ans,get(i)); printf("%d\n",ans); return 0;}
int cc=n/100,ans=0;
while(cc--)
{
int x=rand()%n+1; while(vis[x]) x=rand()%n+1;
vis[x]=1; ans=max(val[x]=get(x),ans);
pos.push((node){val[x],x});
}
while(!pos.empty() && (db)clock()/CLOCKS_PER_SEC<0.95)
{
int x=pos.top().x; pos.pop(); int y=x+1;
if(y<=n && !vis[y]) ans=max(val[y]=get(y),ans),vis[y]=1,pos.push((node){val[y],y});
y=x-1; if(y>=1 && !vis[y]) ans=max(val[y]=get(y),ans),vis[y]=1,pos.push((node){val[y],y});
}
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 3200kb
input:
10 TACCAAAAGC ATTCTTCTAT
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 10
Accepted
time: 68ms
memory: 4640kb
input:
300 AAGGTTCCTGTATTCATTGCATTGCTGAACTACGACCGAGAAATGCAGGCCCGTGGTGAATACATTGCCAGCACACAGTATAAGGTTACCAGCGGTACATGTTTCTAGAAGGCACATTGGGCGGCCCCGACTGGCGGAGACGACGATAACTCTTCGCTCACGTTTACAATGTCTACCGTAGCACTGATGAGGTTTTGTCCCGGGGCTCATAACAAGACTGTAATATACAAACCCACGGTATGCACGGACTACCGATGAGACACACAGCTTACCTGCGCACAAAGCAGTATGGAAAC...
output:
197
result:
ok 1 number(s): "197"
Test #3:
score: 10
Accepted
time: 72ms
memory: 4592kb
input:
300 AGGAGTTATCGTTAGAGGTTTCCCAATTGGACGCCTAGATTAGGAAGGGCACCGACAACAGCTGTCCTAAAGCTACGGGCGCCTATAATGAACACTGAACGTTGCGCCAGTGTCGCGCCCTACCCTGTCCGCGCCGTAGGATTGTCTCAGTCCTTTATGTAAGACTTGCGAAGTCCGTATCCGACAACATATTAGAAACAGATAAGTCGACGGCGAGCGTTGGAACAATCTATCGCGCCTGCCTTAATCCAGCCTGCGTATAAGGTACACGCCCGTTTGATCGCGTTTGTTTATCG...
output:
202
result:
ok 1 number(s): "202"
Test #4:
score: 10
Accepted
time: 69ms
memory: 4636kb
input:
300 TCATAAGTTCCTTGTTTAAGAACAAAGATCAAGGTTCTCCTCCCTGCGACAGGCTGTGACCCCGAACACCTATAGCGTCTTGGCGGAGCGGCTGTTTACACAGGGGCGCTGTTCAATCGATCGATCTCTCGCCGAGTCTGAGTAGCTACTCAAGTCCTTGGTTAGGGAGTCCAACAGAGGACCTGTTGTGACAGATCCTGGTGGAGCTATTAACAGAGTTGCACGTCTCCTATCCTCATCCAAAGTCTGCCCGGGTGGATTGCATGCTGTCCCTAGATAGACGACGTCGCCTACGC...
output:
199
result:
ok 1 number(s): "199"
Test #5:
score: 10
Accepted
time: 939ms
memory: 11012kb
input:
1000 ATTTAGCAGCAGGGAAGTTCAATGGACTCGGGCCGAAACCCGGGTGCGCGTCGCCCGAATACAACGTATCCAGCTGAACAGCCGCCCTACGCACGGTCATGTTGGCACCGGAAGCAATGAATACGGGTCCTAGGTGCCATCGTCACAGGTAAAGATATAGGTCTGACGGGTGGACCTGGGTTTCCCTCGGTGCGATCCCAAGAGCGAATATGCATTGCTTTACGCTCCCTATGTTTAAGCTACGTCCTGACCAAGAGACCCTATCGTTGGTGGCATCGCGAATTACTCTGCTCAT...
output:
657
result:
ok 1 number(s): "657"
Test #6:
score: 0
Wrong Answer
time: 942ms
memory: 11120kb
input:
1000 TCTGCTTTGTGCCAATATCTGACAAGAACACGCCGTGGCGGGTCTTCATATTCGCCCGGACCCATCACGGTATCTTACTGTAGACCGAGATTTGTACATTTCAACCTATACAGGGTCTGGGACGCACTCGTGACTAAAATTTCGTACTTTAGTCAGCACGGGACGCGAGGAGAACATCAAATAATCCTTGATGCAGGCATCTCATCCTTGTCTCCATCTGCGATAAGAGCAATGGGAACATTCCTCCTAAGCGCCGAGTTAAAACGGACAAAAGCCTCCCCGGTCAGTATTGGTG...
output:
652
result:
wrong answer 1st numbers differ - expected: '653', found: '652'
Test #7:
score: 10
Accepted
time: 947ms
memory: 11088kb
input:
1000 GTGTGGGCGTGGGTAGTGCTATCCTCATCCACGATTTCTGCCGGCTCGTTTGTACGCCGGCGTTCGCAGATATTCCGGGTATCGAACTATCATTGATAATCATACGTAAACGCAAGAGCTGGAGTCTTCTTAGAAGGATACGGATGGTGGGGGGTGCCCTCGTGCCAACGGTTTGTGTCACAACACACGTTTTCGACGTCCTCTGAGGGCATTACTGATTGACGGATCATTCTCGTCAACGGCCAGCGCAGGGGACCTACTTAGGGACTTGCCGATCCTGTAGAACTTCGGATCT...
output:
656
result:
ok 1 number(s): "656"
Test #8:
score: 10
Accepted
time: 949ms
memory: 18960kb
input:
2000 TTCATGCGCTCAGCCTGGCTTGAGGCACACGGAGGTGCGCCGCAAACACCTGTTGACTCAAGGGAGCCGACTGCTTGCTGATTCAAATATAATATCTGGGTGAGTTTAACAGTCTCTGTATTAGCGGTGCGGCCTTGTTCAAAGTTACTCGTGATAACCCCACGCTGAAAGACTTCGTACTTTCCCAAGGTTTTGATAGACTCTGAGGGAACTCGGACCAGCCTTTTTCCCTCTGGCGAGGAGAGGCCGGACTCTTTTTGGGAGGCACCTCTTAGCTTCGCCTTCTACGCACCAA...
output:
1307
result:
ok 1 number(s): "1307"
Test #9:
score: 0
Wrong Answer
time: 951ms
memory: 18980kb
input:
2000 AGTACTCACTAGAGAATCCCCGACCACCCAAGTATTACAAACGAATGGAGATTTCTCTTTGTTACCGCTGCGATGCAGCGGCCACCCGATTTGTTGCTCTGGCCACTATTGGAGTTACAGTGTGGAGCACGCTAGACCGTGGCCTGTGGAAGCGTGCTGCCCCAAACGTAAGAACGAACTTATTCGGCTGCAATTCATCGGGCAGGGCGTTACGGCGTACGAGGGCAAGACAAGGTAGGTCCCGCGGACACACTTGCCTATGCCGTAGGAACATGACAATATGAAGATCGGTACC...
output:
1307
result:
wrong answer 1st numbers differ - expected: '1311', found: '1307'
Test #10:
score: 10
Accepted
time: 948ms
memory: 18944kb
input:
2000 GACAACCCCCGTCCATCGGCCTCATAATAAGGGGTGCTGATTTGAAAGTTTTTTCCACTACTGCAGTGAAGCTCTTAGCTGCCGTGTTGACCGCCGCCCTACCAAAGCGAATACAAGCTACTAAACTTCGGACAATAGGATTGCATTCCAGCCAGTGAACGTACGGCACTGTCAGAGTTGCCGACTGATGTCGCGTTGAGTTAGGGCCATGGTCTCGATCTAGCAAGACGGTCACTTTCTTATCTTTCGTGACGGCTAATGTATTTTTGTACAGTGGTCTAAGAAACTTAGTTAG...
output:
1316
result:
ok 1 number(s): "1316"