10192  Vacation
Moderator: Board moderators
10192  Vacation
do we ouput 1 city or 1 cities?
thx
thx

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
i think the judge made a mistake
in the question the soln is obviously the the longest common substring
but if i compare
{
if(strlen(mother)!=strlen(father))
while(1);
gives me a timelimit exceeded
without it my code is running in 0:00:002 time but produces WA
heres is m code
can u help me
but if i compare
{
if(strlen(mother)!=strlen(father))
while(1);
gives me a timelimit exceeded
without it my code is running in 0:00:002 time but produces WA
heres is m code
can u help me
Code: Select all
#include <stdio.h>
#include <string.h>
char a[102],b[102];
int tbl[102][102];
int main()
{
int i,j,na,cno=0,x,y,z,nb;
while(scanf("%s%s",a,b)==2)
{
na=strlen(a);
nb=strlen(b);
for(i=0;i<na+1;i++)
{
tbl[i][0]=0;
}
for(j=0;j<nb+1;j++)
{
tbl[0][j]=0;
}
for(i=0;i<na;i++)
for(j=0;j<nb;j++)
{
x=tbl[i+1][j];
y=tbl[i][j+1];
z=tbl[i][j]+1;
if(a[i]==b[j])
{
tbl[i+1][j+1]=z;
}
else
{
tbl[i+1][j+1]=x>y?(x>z1?x:z1):(y>z1?y:z1);
}
}
printf("Case #%d: you can visit at most %d cities.\n",++cno,tbl[na][nb]);
}
return 0;
}
10192 help plz, Is norm dp enough for this problem??
I used norm dp to try to solve this problem, but I find it difficult to deal with the case like this:
aaab
abaaa
since in my program, I find the lcs first, then deal with the duplicated ones. so, in the case above, I got 1 instead of 2. I guess in this problem we should get 2 as the answer.
so would someone please tell me how to solve such kind of problem??
Thank you!!!
aaab
abaaa
since in my program, I find the lcs first, then deal with the duplicated ones. so, in the case above, I got 1 instead of 2. I guess in this problem we should get 2 as the answer.
so would someone please tell me how to solve such kind of problem??
Thank you!!!

 New poster
 Posts: 9
 Joined: Wed Apr 02, 2003 10:28 am
10192
hello
WanBa said
"
father: abca
mother: abda
according norm DP , the answer is 3.,however,the true is TWO. "
It is totally wrong. I accpeted 10192.
WanBa said
"
father: abca
mother: abda
according norm DP , the answer is 3.,however,the true is TWO. "
It is totally wrong. I accpeted 10192.
10192 run time error
Code: Select all
# include<iostream>
# include<string>
# include<vector>
bool find_(vector<char> &A,int i,char s)
{
for(int j = 0;j <= i;j++)
if(A[j] == s)
return true;
return false;
}
int main()
{
vector<char> A,B;
char c;
int count = 1;
while(cin.get(c))
{
if(c == '#')
break;
while(c != '\n')
{
A.push_back(c);
cin.get(c);
}
cin.get(c);
while(c != '\n')
{
B.push_back(c);
cin.get(c);
}
int **C = new int *[A.size()];
int i,j;
for(i = 0;i < A.size();i++)
{
C[i] = new int[B.size()];
if (find_(A,i,B[0]))
C[i][0] = 1;
else
C[i][0] = 0;
}
for(i = 0;i < B.size();i++)
if(find_(B,i,A[0]))
C[0][i] = 1;
else
C[0][i] = 0;
for(i = 1;i < A.size();i++)
{
for(j = 1;j < B.size();j++)
{
if(A[i] == B[j])
C[i][j] = C[i  1][j  1] + 1;
else
if(C[i  1][j] > C[i][j  1])
C[i][j] = C[i  1][j];
else
C[i][j] = C[i][j  1];
}
}
cout << "Case #" << count <<": you can visit atmost " << C[A.size()  1][B.size()  1] << " cities.\n";
A.erase(A.begin(),A.end());
B.erase(B.begin(),B.end());
for(i = 0;i < A.size();i++)
delete []C[i];
delete []C;
count++;
}
return 0;
}

 Learning poster
 Posts: 55
 Joined: Sat Jan 24, 2004 9:30 pm
 Location: Chittagong
 Contact:
10192
[pascal]var
a,b:string;
cost:array[1..2000,1..2000] of longint;
i,j,k,n:longint;
begin
while a[1]<>'#' do
begin
inc(k);
fillchar(cost,sizeof(cost),0);
readln(a);
if a[1]<>'#' then
readln(b);
if a[1]<>'#' then
begin
for i:=1 to length(a) do
for j:=1 to length(b) do
if a=b[j] then
cost[j]:=1+cost[i1][j1]
else
begin
cost[j]:=cost[j1];
if cost[i1][j]>cost[j] then
cost[j]:=cost[i1][j]
end;
writeln('Case #',k,': you can visit at most ',cost[length(a)][length(b)],' cities.');
end;
end;
end.[/pascal]
Please help me~
a,b:string;
cost:array[1..2000,1..2000] of longint;
i,j,k,n:longint;
begin
while a[1]<>'#' do
begin
inc(k);
fillchar(cost,sizeof(cost),0);
readln(a);
if a[1]<>'#' then
readln(b);
if a[1]<>'#' then
begin
for i:=1 to length(a) do
for j:=1 to length(b) do
if a=b[j] then
cost[j]:=1+cost[i1][j1]
else
begin
cost[j]:=cost[j1];
if cost[i1][j]>cost[j] then
cost[j]:=cost[i1][j]
end;
writeln('Case #',k,': you can visit at most ',cost[length(a)][length(b)],' cities.');
end;
end;
end.[/pascal]
Please help me~