Ai giúp em bài này đi ạ...... em cảm ơn nhiều nhiều ạ... Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước được gọi là đoạn. Cho dãy gồm N số tự nhiên, viết chương trình tìm đoạn ngắnnhất có tổng các phần tử bằng giá trị K cho trước. Input:Tập tin văn bản DOAN.INP + Dòng 1: chứa hai số tự nhiênN, K (1 <=N <=2000); + Các dòng tiếp theo: các phần tử của dãy, mỗi phần tử cách nhau một khoảng trắng. Output:Tập tin văn bản DOAN.OUT, chứa một dòng duy nhất gồm hai số tự nhiên x và b. Trong đó x: là chỉ số đầu đoạn; b: là số phần tử trong đoạn (chiều dài đoạn). Nếu tìm không có (vô nghiệm) ghi 0 0. Ví dụ: DOAN.INP 16 11 4 5 7 6 10 3 6 2 8 12 4 0 0 7 1 1 DOAN.OUT 6 3 DOAN.INP 7 13 4 2 1 5 0 9 3 DOAN.OUT 0 0

Nếu là dãy số không âm thì mình có cách làm như sau:

Biến start=0, end,s=0;
Cho end từ 0->n:

• nếu s < k: s+=a[end]
• nếu s=k. So sánh lấy kq tối ưu. s-= a[start] , start+=1 ( Tính cho lần sau).
• nếu s > k. S-=a[start] , start+=1

Giải thích:
Nếu s < k. Thì tất cả đoạn con [start,end] đều không thoã mãn.
Nếu s=k. Tìm thấy, tính cho lần sau.
Nếu s > k. Tất cả đoạn con bắt đầu từ start và sau end đều lớn hơn k nên không tính các đoan con từ start nữa. Chuyển sang đoạn bắt đầu từ start+1.

dpt O(n)

Mình không biết bạn học ngôn ngữ nào nên mình đã code cả 2 ngôn ngữ là pascal và C++.

C++

#include<iostream>
#include<fstream>
using namespace std;
int main()
{
   int k,n,a[100],tong,j,i,c=123456789,d=0;
   cout<<"n="; cin>>n;
   cout<<"k="; cin>>k;
   for (i=1; i<=n; i++) {
          cout<<"a["<<i<<"]=";cin>>a[i];
   }
 for ( i=1; i<=n; i++) {
      j=i;
      tong=a[i];
      while (j<n && tong<=k && tong+a[j+1]<=k) {
       j++;
       tong+=a[j];
   } 
  if (tong==k && j-i+1<=c-d+1){
    d=i; c=j;
   }
 }
 cout<<d<<" "; if (d != 0) cout<<c-d+1; else cout<<0;   
   return 0; 
}

Pascal

uses crt;
var f:text; i,n,j,d,c,tong,k:longint; a:array[1..1000000]of longint;
begin
clrscr;
   assign(f,'input.pas');reset(f);
      readln(f,n,k);
      while not(eof(f)) do
      begin
         while not(eoln(f)) do begin inc(i); read(f,a[i]); end;  readln(f);
      end;
      d:=0; c:=high(longint)-2;
   close(f);
   assign(f,'output.pas');rewrite(f);
      for i:=1 to n do
         begin
            j:=i;
            tong:=a[i];
            while (j<>n)and(tong<=k)and(tong+a[j+1]<=k) do begin inc(j); inc(tong,a[j]); end;
            if (tong=k)and(j-i+1<c-d+1) then begin d:=i; c:=j;  end;
         end;
   if d=0 then write(f,'0 0')else write(f,d,' ',c-d+1);
   close(f);
end.