### 10192 - Vacation

Posted:

**Thu Oct 03, 2002 6:48 pm**do we ouput 1 city or 1 cities?

thx

thx

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=10&t=26354

Page **1** of **4**

Posted: **Thu Oct 03, 2002 6:48 pm**

do we ouput 1 city or 1 cities?

thx

thx

Posted: **Thu Oct 03, 2002 9:25 pm**

Output "cities" in all cases.

Posted: **Tue Nov 12, 2002 5:36 am**

I think this is just the longest common substring, but I can't get my DP to work.. is there any trick cases or am I using the wrong approach?

Posted: **Tue Nov 12, 2002 5:41 am**

Nevermind. I return dp[x-1][y-1] which didn't work for x or y = 0. Got AC now.

Posted: **Wed Jan 08, 2003 7:02 pm**

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>z-1?x:z-1):(y>z-1?y:z-1);
}
}
printf("Case #%d: you can visit at most %d cities.\n",++cno,tbl[na][nb]);
}
return 0;
}
```

Posted: **Mon Apr 28, 2003 11:43 am**

father: abca

mother: abda

according norm DP , the answer is 3.,however,the true is TWO.

mother: abda

according norm DP , the answer is 3.,however,the true is TWO.

Posted: **Thu Oct 09, 2003 2:11 pm**

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!!!

Posted: **Sun Oct 19, 2003 7:54 am**

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.

Posted: **Tue Jan 20, 2004 6:41 am**

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;
}
```

Posted: **Wed Mar 10, 2004 10:00 am**

so,what is the output for

aaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaa

thanks

aaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaa

thanks

Posted: **Wed Mar 10, 2004 1:02 pm**

input:

aaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaa

WanBa said

"

father: abca

mother: abda

#

output:

Case #1: you can visit at most 8 cities.

Case #2: you can visit at most 0 cities.

Case #3: you can visit at most 9 cities.

aaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaa

WanBa said

"

father: abca

mother: abda

#

output:

Case #1: you can visit at most 8 cities.

Case #2: you can visit at most 0 cities.

Case #3: you can visit at most 9 cities.

Posted: **Sat Jun 12, 2004 8:18 am**

[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[i-1][j-1]*

else

begin

cost*[j]:=cost**[j-1];*

if cost[i-1][j]>cost*[j] then*

cost*[j]:=cost[i-1][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

cost

else

begin

cost

if cost[i-1][j]>cost

cost

end;

writeln('Case #',k,': you can visit at most ',cost[length(a)][length(b)],' cities.');

end;

end;

end.[/pascal]

Please help me~

Posted: **Sat Jun 12, 2004 8:42 am**

Your algorithm seems ok, maybe you can try this:

[pascal]while not eof(input) do

begin

...

readln(a);

if a='#' then exit;

readln(b);

...

end;[/pascal]

Hope it helps

[pascal]while not eof(input) do

begin

...

readln(a);

if a='#' then exit;

readln(b);

...

end;[/pascal]

Hope it helps

Posted: **Sat Jun 12, 2004 10:24 am**

Thanks~

But i still got WA >_<

But i still got WA >_<

Posted: **Sat Jun 12, 2004 10:50 am**

Oops... I forgot to tell you about the array.

The index should start from 0.

[pascal]cost:array[0..2000,0..2000] of longint;[/pascal]

Btw, 2000 is too big, isn't it?

Now it should be AC

The index should start from 0.

[pascal]cost:array[0..2000,0..2000] of longint;[/pascal]

Btw, 2000 is too big, isn't it?

Now it should be AC