[tin học 11] vừa sức thi

[11thanhkhoeo]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cho 1 dãy số nguyên a[1], a[2], …, a[N]. Bạn có thể cộng hoặc trừ mỗi phần tử đi một lượng tối đa là D (dãy số sau khi cộng/trừ có thể xuất hiện số âm hoặc số thực). Hãy tìm độ dài của dây con không giảm dài nhất của dãy số, nếu cộng/trừ các phân tử một cách tối ưu.
Lưu ý: dãy con của dãy số là dãy số a[x[1]], a[x[2]], ..., a[x[k]] (k là một số nguyên) sao cho 1 ≤ x[1] < x[2] < ... < x[k] ≤ N.
Input

• Dòng đầu tiên chứa 2 số nguyên N và D.
• Dòng thứ 2 chứa N số nguyên a[1], a[2], …, a[N], các số được cách nhau bởi ít nhất 1 dấu cách.

Output

• Một dòng duy nhất là độ dài dãy con không giảm dài nhất trong phương án tối ưu.

Giới hạn

• 0 < N ≤ 1000.
• 0 ≤ D ≤ 10^9.
• 0 ≤ a ≤ 10^9.
  [*]Trong 30% số test, D = 0.
  

Example

Input: 4 1
6 4 3 2 Output:
3
Giải thích: Có thể biến đổi dãy thành 6 3 3 3.

 

[p_trk]

 uses crt;
 var
   j,n,d,dem,max:word;
   a:array[1..100] of word;
   dl:array[1..2] of word;
 procedure init;
  var
    i: word;
  begin
     write('nhap n , d : '); readln(n,d);
     for i:=1 to n do
      begin
        write('a[',i,']= ' ); readln(a[i]);
      end;
     max:=0;
     dl[1]:=-d; dl[2]:=d;
  end;

 procedure pro(k:word);
  begin
      if a[k]<=a[k+1] then
       begin
          dem:=dem+1;
          pro(k+1);
       end else exit;
  end;

 procedure dequi;
  begin
     for j:=1 to n do
      begin
        dem:=1;
        pro(j);
        if dem> max then max:=dem;
      end;
  end;
  procedure xuli(m:word);
  var
    l:word;
  begin
     if m=n then dequi;
     for l:=1 to 2 do
      begin
         a[m]:=a[m]+dl[l];
         xuli(m+1);
         a[m]:=a[m]-dl[l];
      end;
  end;
procedure print;
 begin
   write(' kq = ',max);
   readln;
 end;
 BEGIN
  clrscr;
  init;
  dequi;
  print;
 END.

Các huynh sửa giúp đệ lỗi tràn ngăn xếp (~~) Starlove cảm ơn bạn nhiều !!

 

[p_trk]

Bản thân mà mod tin học nhưng Starlove còn phải học hỏi nhiều mong các bạn giúp mình bài này :
chắc ai cũng biết bài toán cổ xếp 8 hậu trên bàn cờ 8*8. bài đó mình đã làm được theo phương pháp đệ qui.
nhưng hiện tai mình đang học bài ngăn xếp (vào trước ra sau ) và hàng đợi ( vào trước ra trước vào sau ra sau ) . thầy mình bảo mình code bài toán 8 hậu theo phương pháp ngăn xếp hoặc hàng đợi , nhờ các huynh giúp Starlove