bzoj 2748 DP

비교적 누드한 가방은 w[i][j]가 I 번째 조작까지 음량 j가 도달할 수 있는지 확인하고 옮기면 된다.
　

/**************************************************************

    Problem: 2748

    User: BLADEVIL

    Language: Pascal

    Result: Accepted

    Time:12 ms

    Memory:284 kb

****************************************************************/

 

//By BLADEVIL

var

    n, s, h                     :longint;

    i, j                        :longint;

    v                           :array[0..60] of longint;

    w                           :array[0..60,0..1000] of boolean;

     

begin

    read(n,s,h);

    for i:=1 to n do read(v[i]);

     

    fillchar(w,sizeof(w),false);

    w[0][s]:=true;

    for i:=1 to n do

        for j:=0 to h do

        begin

            if j-v[i]>=0 then w[i][j]:=w[i][j] or w[i-1][j-v[i]];

            if j+v[i]<=h then w[i][j]:=w[i][j] or w[i-1][j+v[i]];

        end;

    for i:=h downto 0 do if w[n][i] then break;

    if (i=0) and (not w[n][i]) then writeln(-1) else writeln(i);

end.