Đề 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. |
BÌNH LUẬN MỚI