QBSEQ - Dãy con dài nhất có tổng chia hết cho K

Problem

https://vn.spoj.com/problems/QBSEQ

https://oj.vnoi.info/problem/QBSEQ

Cho một dãy gồm n (n <= 1000) số nguyên dương A1, A2, ..., An và số nguyên dương k (k <= 50). Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho k.

Input

Dòng đầu tiên chứa hai số n, k ghi cách nhau bởi ít nhất 1 dấu trống.

Các dòng tiếp theo chứa các số A1, A2, ..., An được ghi theo đúng thứ tự cách nhau ít nhất một dấu trống hoặc xuống dòng

Output

Gồm 1 dòng duy nhất ghi số lượng phần tử của dãy con dài nhất thoả mãn

Example

Input
10 3
2 3 5 7
9 6 12 7
11 15

Output
9

Tutorial

Quy hoạch động như sau:

Trước hết nhận xét ta có thể mod các số của dãy đi k mà không ảnh hưởng đến bản chất bài toán. Gọi F[i][j] là độ dài dài nhất của dãy con xét đến vị trí thứ i sao cho tổng của nó mod k bằng j. Kết quả bài toán là F[n][0].

Tính F[i][j] : Có hai khả năng cho vị trí thứ i : Thứ nhất là không chọn, thì nó là F[i-1][j], nếu chọn thì nó sẽ bằng F[i-1][t]+1 với t là module sao cho khi module của a[i] với t cho k được j. Dễ tính t = (j-a[i]+k)%k.

Do đó F[i][j] = max(F[i-1][j], F[i-1][(j-a[i]+k)%k]+1).

Submission

QBSEQ.cpp

Tutorial SPOJ