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

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

Nhập theo modun k.

f[i,j] là số phần tử lớn nhất của dãy a[1]..a[j] khi chia cho k dư i. f[0,n] là kết quả của bài toán.

f[i,j]=max(f[i-a[j],j-1],f[i,j-1]);

mình làm bài này rồi và đã thử nhiều test thấy đúng nhưng nộp lên trên VNOI lại sai.

Code:: Const MaxN=1000;
MaxK=50;
Var
A:Array[1..MaxN] of integer;
F:Array[0..MaxN+1,0..MaxK-1] of integer;
N,K:integer;

Procedure Input;
Var i:integer;
Begin
Readln(N,K);
For i:=1 to N do Read(A[i]);
End;

Function Sodu(X,Y:integer):integer;
Var Du:integer;
Begin
Du:=(X-Y) mod K;
If Du>=0 then Sodu:=Du
Else Sodu:=Du+K;
End;

Procedure Xuli;
Var i,j:integer;
Begin
F[0,0]:=0;
For j:=1 to K-1 do F[0,j]:=MaxK;
For i:=1 to N do
For j:=0 to K-1 do
Begin
If F[i-1,j]>F[i-1,Sodu(A[i],j)]+1 then F[i,j]:=F[i-1,Sodu(A[i],j)]+1
Else F[i,j]:=F[i-1,j];
End;
End;

Procedure Output;
Var i,S:integer;
Begin
S:=0;
For i:=1 to N do S:=S+A[i];
Writeln(N-F[N,S mod K]);
End;

BEGIN
Input;
Xuli;
Output;
END.

^^ đâu phải lúc nào người ra đề cũng cho test đúng. Với lại có thể cần thêm yêu càu gì đó mà anh ko để ý ^^

Em có cách gì khác không?

Em đâu có học chuyên tin. Với lại em trước giờ tự học là chủ yếu. Ngoài mấy cái liên quan đến toán học đại số hoặc hình học bình thường, thì mấy pp đặc biệt em sao biết.

Gà mờ Tổng số bài gửi : 1 Join date : 04/12/2010

Const MaxN=1000;
MaxK=50;
Var
A:Array[1..MaxN] of integer;
F:Array[0..MaxN+1,0..MaxK-1] of integer;
N,K:integer;

Procedure Input;
Var i:integer;
Begin
Readln(N,K);
For i:=1 to N do Read(A[i]);
End;

Function Sodu(X,Y:integer):integer;
Var Du:integer;
Begin
Du:=(X-Y) mod K;
If Du>=0 then Sodu:=Du
Else Sodu:=Du+K;
End;

Procedure Xuli;
Var i,j:integer;
Begin
F[0,0]:=0;
For j:=1 to K-1 do F[0,j]:=MaxK;
For i:=1 to N do
For j:=0 to K-1 do
Begin
If F[i-1,j]>F[i-1,Sodu(A[i],j)]+1 then F[i,j]:=F[i-1,Sodu(A[i],j)]+1
Else F[i,j]:=F[i-1,j];
End;
End;

Procedure Output;
Var i,S:integer;
Begin
S:=0;
For i:=1 to N do S:=S+A[i];
Writeln(N-F[N,S mod K]);
End;

BEGIN
Input;
Xuli;
Output;
END.

» Dãy chia hết hoàn toàn dài nhất
» Tổng các chữ số
» Xóa số để tạo thành số nhỏ nhất, lớn nhất.
» Chia nhóm từ dãy 1...n*n
» Chìa khóa