Bài Olympic tin học Quy Hoạch Động

MỘT SỐ BÀI TẬP VỀ QUY HOẠCH ĐỘNG

Minh họa:

Cho N số tự nhiên (N tương đối  lớn), hãy tìm dãy con tăng dài nhất của dãy đã cho.
Dữ liệu vào: File daytang.inp gồm

-           Dòng đầu tiên là số N.

-          N dòng tiếp theo là N số tự nhiên.

Dữ liệu ra: File daytang.out gồm 2 số M là chiều dài của dãy tăng dài nhất.
Ví dụ:

1)     Dãy con dài nhất

Cho dãy gồm N số nguyên (N £ 10000), mỗi số nằm trong khoảng -30000 đến 30000. Hãy chọn ra trong dãy này một dãy con nhiều phần tử nhất mà tổng của hai phần tử liên tiếp là số nguyên tố.

2)      CẤP SỐ CỘNG

Cho một dãy gồm N (N rất lớn) số nguyên a₁, a₂, a₃,..,a_n với |a_i| £ 30000 (i = 1, 2..N).  Hãy tìm trong dãy A đó một dãy con dài nhất lập thành một dãy cấp số cộng có
công sai là d (0 < d £ 100).

Dữ liệu vào: đọc từ file văn bản CSCONG. INP, trong đó
- Dòng đầu ghi số N
- dòng tiếp theo ghi N số là các số ứng với dãy A.

Dữ liệu ra: ghi ra file văn bản CSCONG.OUT, gồm
- Dòng đầu ghi số M là số phần tử và công sai của dãy cấp số cộng đó
- Dòng tiếp theo ghi M số là chỉ số của các số thuộc cấp số cộng từ dãy ban đầu.

Ví dụ:

CSCONG.INP 10 1 2 3 -6 3 8 5 6 7 -4

CSCONG.OUT 4 2 1 3 7 9

3)      Đổi tiền

Một ngân hàng có N loại tiền mệnh giá A[1],A[2],..A[N] với số tiền không giới hạn cần chi trả cho khách hàng một số tiền M đồng. Cho biết M, N, A[i] là các số nguyên và N≤100; M≤32000; 

Yêu cầu: Tìm cách trả sao cho số lượng tờ là ít nhất.

            - Dữ liệu vào file DOITIEN.INP có dạng

            - Dòng 1 ghi 2 số N, M 

            - Dòng 2 ghi N số nguyên dương A[1], A[2],.., A[N]

Kết quả ra file DOITIEN.OUT có dạng 

            - Nếu không có cách trả ghi ra file một dòng duy nhất ″No Solution″ 

            - Nếu có cách trả dòng một ghi ra số lượng tờ ít nhất phải trả, dòng 2 ghi N số ứng với số tờ cần trả cho mỗi loại tiền. 

Ví dụ:

DOITIEN.INP 3 12 4 10 3

DOITIEN.INP 3 3 0 0

4)     XẾP HÀNG MUA VÉ

Có N người xếp hàng mua vé. Ta đánh số họ từ 1 đến N theo thứ tự đúng trong hàng. Thời gian phục vụ bán vé cho người thứ i là t_i. Mỗi người cần mua một vé nhưng được quyền mua tối đa 2 vé, vì thế một số người có thể nhờ người đứng ngay trước mình mua hộ. Người thứ i nhận mua vé cho người thứ i+1 thì thời gian mua vé cho 2 người là r_i. Tìm phương án sao cho N người đều có vé với thời gian ít nhất.

Dữ liệu vào từ file văn bản TICK.INP có cấu trúc:

-         Dòng thứ nhất ghi số N (1 < N  ≤ 2000);

-         Dòng thứ hai ghi N số nguyên dương t₁, t₂, …, t_N

-         Dòng thứ ba ghi N – 1 số r₁, r₂, …, r_N-1

Kết quả ghi ra file văn bản TICK.OUT gồm:

-         Dòng thứ nhất ghi tổng thời gian phục vụ bán vé

-         Dòng tiếp theo ghi chỉ số của các khách hàng cần rời khỏi hàng (nếu không có ai thì quy ước ghi số 0).

Ví dụ:

TICK.INP 5 2 5 7 8 4 3 9 10 10

TICK.OUT 17 2 4

Hướng dẫn: Quy hoạch động (L[i]: Thời gian ít nhất khi xét đến người thứ i, trong đó người thứ i có thể tự mua vé hoặc nhờ người thứ i – 1 mua vé)

5)     Lập kế hoạch

Một sinh viên của một trường Đại học dự định lập kế hoạch học tập cho kỳ thi sắp tới của mình. Số môn học trong học kỳ là N và khoảng thời gian còn lại để sinh viên đó học bài là T. Mỗi môn học có số học trình là S_i. Khi tính điểm tổng kết học kỳ, điểm thi một môn i được nhân với số học trình S_i của môn đó vì số học trình càng cao thì lượng kiến thức đào tạo môn đó càng nhiều.

Điểm thi của môn học tùy thuộc vào lượng thời gian anh ta dành cho môn đó. Anh ta không muốn thi lại bất kỳ môn nào (điểm phải từ 5 trở lên) và muốn có điểm tổng kết cao nhất. Hãy giúp sinh viên này phân bố thời gian học cho các môn.

Dữ liệu vào lấy từ file văn bản HOCTRINH.INP gồm 3 dòng:

-         Dòng đầu tiên ghi số N và T;

-         Dòng tiếp theo là các số S_i ( 1≤ i ≤ N)

-         N dòng tiếp theo: dòng thứ i trong N dòng này ghi 6 số thể hiện số giờ tối thiểu để anh ta đạt được điểm lần lượt là 5 đến 10.

Kết quả ghi ra file văn bản HOCTRINH.OUT

-         Dòng đầu tiên ghi tổng điểm của N môn (đã tính hệ số học trình).

-         N dòng tiếp theo, dòng thứ i ghi thời gian mà anh ta đầu tư cho môn thứ i.

Ví dụ:

HOCTRINH.INP 3  12 1  2  2 1  2  3  4  5  6 1  2  3  4  5  6 1  2  3  4  5  6

HOCTRINH.OUT 4  3 1 5 6

6)      Chuỗi con chung dài nhất

    Cho hai chuỗi A = a₁a₂...a_n và B = b₁b₂...b_m, tìm chuỗi con chung dài nhất của hai chuỗi a và b.

ví dụ: A = ABCAXTYAB và B = QUABAXTBCA

kết quả là chuỗi con dài nhất là (AXT) hoặc (BCA).

7)      Bài tam giác (Triangle)

   

            7

          3   8

        8   1   0

      2   7   4   4

    4   5   2   6   5   (a)

    Hình 1 biểu diễn tam giác số. Hãy viết chương trình tính tổng lớn nhất các số trên con đường bắt đầu từ đỉnh và kết thúc đâu đó ở đáy.
    - Mỗi bước có thể đi chéo xuống phía trái hoặc đi chéo xuống phía phải.

-          Số lượng dòng trong tam giác lớn hơn 1 nhưng bé hơn 100.

-          Các số trong tam giác điều là số nguyên từ 0 đến 99.

8)      Chuỗi con đối xứng dài nhất

Cho một xâu ký tự có độ dài không quá 5000 ký tự. Hãy tìm chuỗi con đối xứng dài nhất từ chuỗi đã cho. (Khi đảo ngược chuỗi này ta vẫn được chuỗi đó).

Yêu cầu: Số ký tự thêm là ít nhất và thời gian chạy không quá 2 giây.

Input: file text có tên PALIN.INP gồm:

-         Dòng 1 số nguyên n: độ dài của chuỗi. (1<=n<=5000)

-         Dòng 2 là chuỗi ký tự. Không có dấu cách.

Output: file text có tên là PALIN.OUT gồm: Chuỗi con tìm được.

Ví dụ:

PALIN.INP 6 abcdba

PALIN.INP abcba

9)      Đường đi trên bảng số

Cho một bảng A kích thước m_xn gồm các số nguyên. Tại mỗi ô (x, y) có thể đi đến được 4 ô kề cạnh. Bài toán đặt ra là tìm đường đi từ ô (1, 1) đến ô (m, n) sao cho tổng các ô đi qua là nhỏ nhất có thể được.

10)  Dãy con không giảm dài nhất

Cho dãy số nguyên dương a₁,a₂,...,a_n.

Dãy số

a_i, a_i+1,..., a_j thỏa mãn a_i ≤ a_i+1 ≤...≤ a_j

với 1≤ i ≤ j ≤ n được gọi là dãy con không giảm của dãy số đã cho và khi đó số j-i+1 được gọi là độ dài của dãy con này.

Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số {u_k} xác định bởi u₁ = 1, u_k = u_k-1+ k (k ≥ 2), hãy tìm dãy con có độ dài lớn nhất.

Dữ liệu: Vào từ file văn bản MAXISEQ.INP:

·         Dòng đầu tiên chứa một số nguyên dương n (n ≤10⁴);

·         Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương a_i (a_i ≤10⁸) là số hạng thứ i của dãy đã cho, i = 1, 2, …, n.

Kết quả: Ghi ra file văn bản MAXISEQ.OUT số nguyên d là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0).

Ví dụ: Cho dãy số có 8 phần tử: 2, 2007, 6, 6, 15, 16, 3, 21. Các dãy con không giảm  của dãy số đã cho mà các phần tử của nó đều thuộc dãy {u_k} là: 6, 6, 15 và
3, 21 (vì u₂ = 3, u₃ = 6, u₅ = 15, u₆ = 21). Dãy cần tìm là 6, 6, 15 có độ dài 3.

MAXISEQ.INP	MAXISEQ.OUT
8 2 2007 6 6 15 16 3 21	3

11)  CƠ SỐ NHỊ PHÂN ÂM

Xét số nhị phân biểu diễn theo cơ số B = -2. Khi đó, nếu X= x_n x_n-1...x₁x₀, x_I Î {0, 1}, i = n, n-1, …, 1, 0.

Sang cơ số 10, ta có X = x_n*(-2)ⁿ + x_n-1*(-2)^n-1 + . . . + x₁*(-2)¹ + x₀ .

Ví dụ: X = 11010 ở cơ số -2. Đổi sang cơ số 10, ta có:

 X = 1*(-2)⁴ + 1*(-2)³ + 0*(-2)² + 1*(-2)¹ + 0

     =  16 - 8 + 0 - 2

     = 6

Với cơ số -2, ta có thể biểu diễn các số âm cũng như số dương, không cần phải có bít dấu riêng.

Ví dụ: 6 = 11010,  -6 = 1110.

Yêu cầu: Cho 2 số X  và  Y ở dạng nhị phân cơ số -2, hãy tính X+Y , X-Y và đưa ra dưới dạng biểu diễn nhị phân cơ  số -2.

Dữ liệu: Vào từ file văn bản NEGBIN.INP các số nguyên X  và  Y ở dạng nhị phân cơ số -2, mỗi số trên một dòng dưới dạng xâu ký tự 0, 1, không có số 0 không có nghĩa ở đầu, số lượng các chữ số không quá 200.

Kết quả: Đưa ra file văn bản NEGBIN.OUT tổng và hiệu ở dạng nhị phân cơ số -2, mỗi giá trị trờn một dòng, không có số 0 không có nghĩa ở đầu.

Ví dụ:

NEGBIN.INP		NEGBIN.OUT
11010 100		11110 110