KVIP – spoj

Đề bài:

Thuật toán:

Giả sử người 1 (VIP) ngồi ở vị trí k1 thì:

– Người 2,3,…,k1-1 sẽ ngồi đúng vị trí của mình: 2,3,…,k1-1

– Người k1 có 2 cách chọn vị trí ngồi:

— Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

— Chọn ngồi ở vị trí k2>k1: người k1+1,k1+2,…,k2-1 sẽ ngồi đúng vị trí

— Người k2 có 2 cách chọn vị trí ngồi:

——– Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

——– Chọn ngồi ở vị trí k3: người k2+1,k2+2,…,k3-1 sẽ ngồi đúng vị trí

……

 

Đề bài quy về chọn 1 dãy các phần tử: k1,k2,k3,…,kx,1 ( với k1<k2<k3…<kx )

Tức là:

– Người 1 ngồi vị trí k1

– Người k1 ngồi vị trí k2

– Người k2 ngồi vị trí k3

– Người kx-1 ngồi vị trí kx

– Người kx ngồi vị trí 1

– Những người còn lại ngồi đúng vị trí của mình

 

Kết quả của dãy đã chọn là:

A[1,1] + A[2,2] + … + A[n,n] – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]

Đặt S=A[1,1] + A[2,2] + … + A[n,n], S không đổi

=> Cần tìm dãy sao cho:

(- A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]) đạt giá trị lớn nhất

Gọi F[i] là tổng lớn nhất của dãy {k1,k2,…,i,1} ( người i ngồi vị trí 1 )

  • F[i] = – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1] ( với kx=i )
  • F[i] = max ( F[i], F[j] – A[j,1] + A[j,j] + A[i,1] – A[i,i] ) với ( i>j )

Kết quả bài toán: S + F (max)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
 
var     a       :Array[1..maxN,1..maxN] of longint;
        f       :Array[1..maxN] of int64;
        n       :longint;
 
procedure Optimize;
var     i , j   :longint;
        ans :int64;
        maxF    :int64;
begin
        f[1]:=0;
        for i:=1 to n do f[1]:=f[1]+a[i,i];
        for i:=2 to n do
                begin
                        f[i]:=low(int64);
                        for j:=i-1 downto 1 do
                                f[i]:=max(f[i],f[j]-a[j,1]+a[j,i]-a[i,i]+a[i,1]);
                end;
        maxF:=f[1];
        for i:=2 to n do maxF:=max(maxF,f[i]);
        writeln(maxF);
end;
 
procedure run;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(a[i,j]);
        Optimize;
        close(input);close(output);
end;
 
begin
        run;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*