NKPALIN - 0.43s

Tiêu đề: NKPALIN - 0.43s Mon Oct 24, 2011 4:45 pm

ĐỀ BÀI:

Trích dẫn :: Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.

Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.
Dữ liệu vào

Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.
Kết qủa

Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.
Giới hạn

Chuỗi s có độ dài không vượt quá 2000.
Ví dụ

Dữ liệu mẫu
lmevxeyzl

Kết qủa
level

THUẬT TUÁN:

+ Tương tự bài QBSTR chuỗi 2 là chuỗi đảo của chuỗi 1, khác ở chỗ là ta có đánh dấu lại rồi đếm ngược lại những chỗ đã đánh dấu.

SOURCE CODE:

Code:: import java.util.Scanner;
class Test
{
public static void main(String[] args)
{
Scanner nhap = new Scanner(System.in);
String a = nhap.nextLine();
String s = "";
char c1[] = a.toCharArray();
int cLen = c1.length + 1;
char c2[] = new char[cLen-1];
int[][] p = new int[400][400];
int[][] q = new int[400][400];
int u = 0;
for( int i = cLen-1; i>=1; i-- ){
p[i][0] = 0;
p[0][i] = 0;
c2[u] = c1[i-1];
u++;
}
u = 0;
for( int i = 1; i < cLen; i++ ) {
for( int j = 1; j < cLen; j++ ) {
if( c1[i-1] == c2[j-1] ) {
p[i][j] = p[i-1][j-1] + 1;
q[i][j] = 1;
}else{
p[i][j] = Math.max( p[i-1][j], p[i][j-1] );
}
}
}
for( int i = 0; i < cLen; i++ ) {
for( int j = 0; j < cLen; j++ ) {
if( p[i][j] > u )
u = p[i][j];
}
}
for( int i = cLen-1; i>=1;i-- ) {
for( int j = cLen - 1; j >= 1 ; j-- ) {
if( p[i][j] == u && q[i][j] == 1 ){
s += c1[i-1];
u--;
}
}
}
System.out.print(s);
}
}

Mà sao nó chạy có 0.34s nhỉ, cái kia chạy tới 4s?

Tiêu đề: Re: NKPALIN - 0.43s Mon Oct 24, 2011 10:44 pm

Rất tốt!!

Thời gian chạy đó là chạy hết tất cả các test, nếu bài đó nhiều test thì thời gian chạy hết các test sẽ lâu hơn các bài ít test