Tìm dãy con của một dãy

[lemon191]

Ai làm ơn chỉ giúp tui cách giải các bài tìm dãy con với! Mãi mà tui vẫn chẳng bit làm thế nào? Hix
Vd: Cho n số nguyên a1, a2,…,an. Tìm dãy con của dãy a có tổng bằng s <=40000., n<=200. Mỗi phần tử của dãy a chỉ sử dụng tối đa 1 lần.
Dữ liệu vào: Cho từ tệp Daycon.inp có dòng 1 chứa số n và s, dòng 2 chứa n số nguyên của dãy a.
Kết quả: Ghi vào tệp Daycon.out dãy tìm được

Daycon.inp
Daycon.out
5 10
2 3 4 8 1
2 3 4 1

[92A01]

Theo như đề thì dãy con 2 8 cũng là một kết quả đúng không?
Bài yêu cầu tìm nhiều kết quả hay chỉ một?

[lemon191]

đề chính xác là như thế này cơ các bác ah!
Input
5 10
2 3 4 8 1
Output
2 3 4 1

[lemon191]

2 8
cũng là 1 kết quả đấy bác ah!
Em mong các bác chỉ dẫn tận tình cách làm các bài toán dạng như vậy!
Em đầu óc tối tăm mãi mà vẫn k biết cách làm
Thanks

[myhanh]

Giải thuật thoạt xuất hiện trong đầu nên chưa chắc là tốt nhất:
1) Xây dựng đồ thị:
Xem mỗi phần từ ai của dãy là một đỉnh của đồ thị có hướng. Cạnh của đồ thị aiaj với (i < j). Trọng lượng cạnh là ai.
Lưu ý trong quá trình xây dựng đồ thị cần loại bỏ các ai >= s.
2) Áp dụng giải thuật LLoyd để tìm đường đi 2 đỉnh đồ thị. Sau đó in ra đường đi nào có độ dài s-d (với d là đỉnh cuối của đường đi).

[lemon191]

em cám ơn bác myhanh nhưng thực sự là với đồ thị thì em lại càng mù tịt hơn.
Em nhìn vào chỉ như nhìn bức vách thui.
Em chỉ là gà đang tập tọe học lập trình thui mà. Mong các bác pro chỉ giáo

em có bài này nữa mong các bác ra tay kíu giúp
Đoạn con
Cho dãy số nguyên không âm a1, a2, …an. Chia dãy trên thành đoạn con liên tiếp sao cho tổng giá trị các phần tử của các đoạn con đều bằng nhau và số đoạn con là lớn nhất.
Dữ liệu vào trong file Doancon.inp có dạng:
- Dòng đầu ghi số nguyên dương n là số phần tử có trong dãy (n <= 1000)
- Các dòng tiếp theo ghi lần lượt các phần tử thuộc dãy.
Dữ liệu ra trong file Doancon.out
- Dòng đầu ghi số p, q là số đoạn con và tổng giá trị của mỗi đoạn con.
- P dòng tiếp theo mỗi dòng ghi số d và b là chỉ số của phần tử đầu và phần tử kết thúc 1 đoạn con trong dãy đã cho.
Ví dụ:
Doancon.inp
Doancon.out
10
1 3 5 9 7 2
4 1 4
9
5 9
1 3
4 4
5 6
7 9
10 10

[92A01]

Nguyên văn bởi lemon191

Ai làm ơn chỉ giúp tui cách giải các bài tìm dãy con với! Mãi mà tui vẫn chẳng bit làm thế nào? Hix
Vd: Cho n số nguyên a1, a2,…,an. Tìm dãy con của dãy a có tổng bằng s <=40000., n<=200. Mỗi phần tử của dãy a chỉ sử dụng tối đa 1 lần.
Dữ liệu vào: Cho từ tệp Daycon.inp có dòng 1 chứa số n và s, dòng 2 chứa n số nguyên của dãy a.
Kết quả: Ghi vào tệp Daycon.out dãy tìm được

Daycon.inp
Daycon.out
5 10
2 3 4 8 1
2 3 4 1

Em dùng ngăn xếp thử xem.

[lemon191]

em cám ơn các bác rất nhìu!
Các bác cho e bít làm thế nào mà các bác lập trình giỏi đc k ah!