https://oj.luyencode.net/problem/PUSHUPS

[utterances-bot]

Chi tiết bài tập - Luyện Code Online

https://oj.luyencode.net/problem/PUSHUPS

[trantrunghieu123]

Gợi ý

Với bài này mình nghĩ có thể quy hoạch động gọi f[i] là số điểm tối đa của i lần chống đẩy từ gợi ý đề bài thì có thể nhận ra là đây sẽ tính tăng dần vd: 3 2 4 thì lần đầu chống đẩy 3 cái tiếp theo sẽ chống đẩy 3+2 cái rồi tiếp theo lại chống đẩy 3+2+4 cái dễ nhận ra là tổng lần đầu sẽ là 3. Còn tổng tiếp theo sẽ là (3+3)+2=8. tiếp nữa sẽ là 8+(3+2)+4 mà 3 ở đợt 2 chính là tổng các ghi điểm của cách trước đó 3+2 ở đợt 3 cũng vậy. Nên ở đây ta sẽ có công thức truy hồi như sau: dp[i]=max(dp[i],dp[j]+r[k]) với j+dp[j]+r[k]=i. với j: 0<=j

[anle12345]

Bài này mình dùng mảng 2 chiều nên chắc sẽ không gọn bằng anh trantrunghieu123 trên kia đâu:)) Ai dùng Pascal thì có thể tham khảo code này tại mình code bằng pascal. Đây là lời giải của mình đã AC. Nếu bạn đã cố gắng mà chưa làm được thì có thể tham khảo lời giải của mình.

Xem code AC

uses crt; var i,n,j,k,S,x,t:longint; f:array[0..10000,0..10000] of longint; a:array[0..10000] of longint; begin clrscr; read(S); read(n); for i:=1 to n do read(a[i]); f[0,0]:=1; t:=0; for j:=0 to s do for i:=0 to t do if f[i,j]=1 then for k:=1 to n do begin f[i+a[k],j+i+a[k]]:=1; if i+j+a[k]<=s then if i+a[k]>t then t:=i+a[k]; end; x:=0; for i:=0 to s do if f[i,s]=1 then x:=i; clrscr; if x=0 then write(-1) else write(x); readln; readln; end.