Nguồn đề bài: http://www.spoj.com/PTIT/problems/P157PROE/
1. Đề bài P157PROE spoj
Một cửa hàng đá quý và trang sức nhận thấy rằng các viên kim cương sẽ càng hấp dẫn với người mua hơn nếu trọng lượng càng nhỏ và độ trong suốt càng cao. Cho trước N viên kim cương. Giả sử trọng lượng viên kim cương thứ i được biểu diễn bởi một số thực wi từ 0.0 đến 10.0. Còn độ trong suốt thì cho bởi số thực ci, cũng trong khoảng từ 0.0 đến 10.0. Hãy tìm ra độ dài dãy con dài nhất có thể trong đó trọng lượng thì tăng dần còn độ trong suốt thì giảm dần.
Ví dụ, với 6 viên kim cương có các giá trị biểu diễn như sau:
Một cửa hàng đá quý và trang sức nhận thấy rằng các viên kim cương sẽ càng hấp dẫn với người mua hơn nếu trọng lượng càng nhỏ và độ trong suốt càng cao. Cho trước N viên kim cương. Giả sử trọng lượng viên kim cương thứ i được biểu diễn bởi một số thực wi từ 0.0 đến 10.0. Còn độ trong suốt thì cho bởi số thực ci, cũng trong khoảng từ 0.0 đến 10.0. Hãy tìm ra độ dài dãy con dài nhất có thể trong đó trọng lượng thì tăng dần còn độ trong suốt thì giảm dần.
Ví dụ, với 6 viên kim cương có các giá trị biểu diễn như sau:
Input
Dòng đầu tiên ghi số bộ test (không quá 100).
Mỗi bộ test bắt đầu bằng số N là số viên kim cương (1<=N<=200). Tiếp theo là N dòng, mỗi dòng ghi lần lượt 2 số thực wi và ci (đều trong khoảng từ 0.0 đến 10.0)
Output
Với mỗi bộ test, ghi ra trên một dòng giá trị độ dài của dãy con dài nhất có thể.
Example
Input:
Output:
2
1
4
2. Hướng dẫn P157PROE spoj PTIT
– Đây là bài toán QHĐ tìm dãy con tăng đơn điệu dài nhất.
– gọi F[i] là độ dài dãy con thỏa mãn đề bài có phần tử cuối cùng là i
– khởi tạo F[0]=0, W[0]:= âm vô cực, C[0]:= dương vô cực, F[i]=0.
-Nếu W[i]>W[j] và C[i]<C[j] thì F[i]:=max(F[i],F[j]+1); (i=1..n, j=0..i-1).
– Đáp án = Max(F[i]) (i=1..n).
3. code tham khảo P157PROE spoj PTIT
const fi='';
nmax=200;
type data=longint;
var
f:text;
A,B:array[0..nmax+1] of real;
C:array[0..nmax+1] of data;
n,test:data;
function max(a,b:data):data;
begin
if a>b then exit(a); exit(b);
end;
procedure xuli;
var i,j,res:data;
begin
C[0]:=0;
A[0]:=low(data);
B[0]:=high(data);
res:=0;
//goi c[i] la do dai day con thoa man ket thuc tai i
for i:=1 to n do
begin
c[i]:=0;
for j:=0 to i-1 do
if (A[i]>A[j]) and (B[i]<B[j]) then
C[i]:=max(C[i],C[j]+1);
res:=max(res,c[i]);
end;
writeln(res);
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,test);
for i:=1 to test do
begin
readln(f,n);
for j:=1 to n do
readln(f,a[j],b[j]);
xuli;
end;
close(f);
end;
begin
docfile;
end.
