多線程 DP。

真心覺得這個方程不好想！

設f[k,i,j,l]， 表示走第k步，第一個人，第二個人和第二個人各走到第I行，第j行和第L行所能得到的最優解（我們規定前一個人比后一個人先走！）。

狀態轉移：

規定 t[1]:=0; t[2]:=-1;

for w:=1 to 2 do

　　for q:=1 to 2 do

　　　　for p:=1 to 2 do

　　f[k,i,j,l]:=max(f[k,i,j,l],f[k-1,i+t[w],i+t[q],l+t[p]])

共有八種狀態轉移的方式！

接下來：由于更新了 i,j,l 并規定了前一個人比后一個人先走所以：

有 f[k,i,j,l]:=f[k,i,j,l]+s[i,k-i+1].

接下來，如果有i<>j說明 第二個人當前的狀態還沒有人走過，所以我們可以

f[k,i,j,l]:=f[k,i,j,l]+s[j,k-j+1].

同理 如果有 l<>j 且 l<>i 我們有：

f[k,i,j,l]:=f[k,i,j,l]+s[j,k-l+1].

我們共要走 2*n-1步。

所以 ans:=f[2*n-1,n,n,n].

1 rogram p1143; uses math;2 const3 t:array[1..2]of longint=(0,-1);4 var5 i,j,k,l,m,n,w,p,q:longint;6 f:array[0..41,-20..20,-20..20,-20..20]of longint;7 s:array[0..20,0..20]of longint;8 begin9 read(n); 10 for i:=1 to n do 11 for j:=1 to n do 12 read(s[i,j]); 13 for k:=1 to 2*n-1 do 14 for i:=1 to k do 15 for j:=1 to k do 16 for l:=1 to k do 17 begin 18 begin 19 for w:=1 to 2 do 20 for p:=1 to 2 do 21 for q:=1 to 2 do 22 f[k,i,j,l]:=max(f[k,i,j,l],f[k-1,i+t[w],j+t[p],l+t[q]]); 23 end; 24 f[k,i,j,l]:=f[k,i,j,l]+s[i,k-i+1]; 25 if(i<>j)then f[k,i,j,l]:=f[k,i,j,l]+s[j,k-j+1]; 26 if(i<>l)and(j<>l)then f[k,i,j,l]:=f[k,i,j,l]+s[l,k-l+1]; 27 end; 28 write(f[2*n-1,n,n,n]); 29 end.

這種類型的題目還要多加練習....

轉載于:https://www.cnblogs.com/zyxx233/archive/2012/12/08/2809217.html

總結

以上是生活随笔為你收集整理的vijos p1143(三取方格数)（100）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。