Solution_tuần 1

HSPC14A - Biến đổi cặp số 

Bài toán này , để đơn giản , ta sẽ làm ngược bài toán : 

từ 2 số (a,b) sử dụng các thao tác:

+(a , a-b) (nếu a>b)

+ (b, b-a) (nếu b>a)

sao cho đưa về trạng thái (1,1)

nhận thấy đấy chính là thao tác tìm UCLN của 2 số

Do số test nhỏ <= 10 nên ta có giải thuật đơn giản sau:

+ với mỗi số X , ta cần tìm Y để sao cho số UCLN (X,Y) = 1 và số bước tìm UCLN min 

+ Giờ đây ta có hàm F(x,y) là số bước đưa số X,Y về trạng thái (1,1) --> F(x,y) == F(y%x, x) + y/x;

( với y>=x) 

Dưới đây là code của mình : http://ideone.com/zDKK0N 

AMSSEQ - Dãy số

bài toán này mang tầm vóc quy hoạch động cơ bản : 

gọi F[i] là tổng số tiền tối đa nếu bước cuối cùng là i

Do ta không được bước quá k bước , nếu bước trước của i có thể là i-1,i-2,...i-k+1.

=> F[i] = max (F[j] + a[i] ) (j = i-k+1...i-1) 

kết quả sẽ là max (F[i] ) (i <= n) 

Code của mình : http://ideone.com/iZgXo7