首先，這是一道DP題，雖然說有簡便的做法，但我還是采用了插頭DP的方法（不知道是不是插頭DP，可能是輪廓線DP）
You are given a rectangular table 3?×?n. Each cell contains an integer. You can move from one cell to another if they share a side.
Find such path from the upper left cell to the bottom right cell of the table that doesn’t visit any of the cells twice, and the sum of numbers written in the cells of this path is maximum possible.
The first line contains an integer n (1?≤?n?≤?105) — the number of columns in the table.
Next three lines contain n integers each — the description of the table. The j-th number in the i-th line corresponds to the cell aij (?-?109?≤?aij?≤?109) of the table.
Output the maximum sum of numbers on a path from the upper left cell to the bottom right cell of the table, that doesn’t visit any of the cells twice.
3 1 1 1 1 -1 1 1 1 1
7
5 10 10 10 -1 -1 -1 10 10 10 10 -1 10 10 10 10
110
The path for the first example:
The path for the second example:
好了，那么這道題其實就是要求不重復經過某個方格，求從左上角到右下角的路徑上權值和最大值。注意本題方格中的權值可以為負
我曾經參加過這次比賽，然而時間太短寫不完。我知道本題應該有簡便的DP方法，但我覺得正常的思路還是先使用插頭DP（還是輪廓線DP）的方法。因為本題是一個窄棋盤（3*n）所以我們可以枚舉一個豎列的所有情況，作為參數，進行狀態轉移
不多說，貼代碼（使用這種方法寫的代碼十分丑。。。）
#include<cstdio>#include<cstdlib>#define maxn 100005#define maxn2 18#define LL long long int#define k1 ans=max(ans,DP(pos+1,1)+geo[pos+1][0]) #define k2 ans=max(ans,DP(pos+1,2)+geo[pos+1][1]) #define k3 ans=max(ans,DP(pos+1,3)+geo[pos+1][2]) //#define k4 ans=max(ans,DP(pos+1,4)+geo[pos+1][0]+geo[pos+1][1]) //#define k5 ans=max(ans,DP(pos+1,5)+geo[pos+1][0]+geo[pos+1][2]) //#define k6 ans=max(ans,DP(pos+1,6)+geo[pos+1][2]+geo[pos+1][1]) #define k7 ans=max(ans,DP(pos+1,7)+geo[pos+1][0]+geo[pos+1][1]+geo[pos+1][2]) #define k8 ans=max(ans,DP(pos+1,8)+geo[pos+1][0]+geo[pos+1][1]+geo[pos+1][2]) #define k10 ans=max(ans,DP(pos+1,10)+geo[pos+1][0]+geo[pos+1][1]+geo[pos+1][2]) #define k11 ans=max(ans,DP(pos+1,11)+geo[pos+1][0]+geo[pos+1][1]+geo[pos+1][2]) #define k12 ans=max(ans,DP(pos+1,12)+geo[pos+1][0]+geo[pos+1][1]) #define k13 ans=max(ans,DP(pos+1,13)+geo[pos+1][0]+geo[pos+1][1]+geo[pos+1][2]) #define k14 ans=max(ans,DP(pos+1,14)+geo[pos+1][2]+geo[pos+1][1]) #define k15 ans=max(ans,DP(pos+1,15)+geo[pos+1][0]+geo[pos+1][1]) #define k16 ans=max(ans,DP(pos+1,16)+geo[pos+1][0]+geo[pos+1][1]+geo[pos+1][2]) #define k17 ans=max(ans,DP(pos+1,17)+geo[pos+1][2]+geo[pos+1][1]) #define k18 ans=max(ans,DP(pos+1,18)+geo[pos+1][0]+geo[pos+1][1]+geo[pos+1][2])using namespace std;LL max(LL a,LL b){ if(a>b)return a; return b;}/*Stable...... 1 2 3 4 5 6 7 8 NULL 10 11 12 13 14 15 16 17 18 -------------------------------------------------------------------------------------------------------------------------------| | | | | | | | | | | | | | | | | | ||******| | |******|******| |******|**** |*** |******| ***|**** |**** | | ***| ***| |******|| | | | | | | | * | * | | * | * | * | | * | * | | |-----------------------------------------------------*-----*--------------*------*------*-------------*------*-----------------| | | | | | | | * | * | | * | * | * | | * | * | | || |******| |******| |******|**** |**** | * | ***| ***| ***| * |**** |**** | * | ***|******|| | | | | | | * | | * | * | | | * | * | | * | * | | ----------------------------------------------*------------*-------*--------------------*------*-------------*------*-----------| | | | | | | * | | * | * | | | * | * | | * | * | | | | |******| |******|******|**** |******|*** | ***|******| | ***| ***| |**** |**** |******|| | | | | | | | | | | | | | | | | | |-------------------------------------------------------------------------------------------------------------------------------------------*/LL INF;LL dp[maxn][maxn2];LL geo[maxn][3];int n;LL DP(int pos,int op){ if(dp[pos][op])return dp[pos][op]; LL& ans=dp[pos][op]=-INF; if(pos==n-1){ if(op==3||op==8||op==13||op==14)return ans=0; return ans; } else{ switch(op){ case 1:{ k1;k10;k12;k13; return ans; break; } case 2:{ k2;k14;k15; return ans; break; }case 3:{ k3;k11;k16;k17; return ans; break; }case 7:{ k1;k10;k12;k13; return ans; break; }case 8:{ k3;k11;k16;k17; return ans; break; }case 10:{ k18;k8; return ans; break; }case 11:{ k18;k7; return ans; break; }case 12:{ k2;k14;k15; return ans; break; }case 13:{ k3;k11;k16;k17; return ans; break; }case 14:{ k3;k11;k16;k17; return ans; break; }case 15:{ k1;k10;k12;k13; return ans; break; }case 16:{ k1;k10;k12;k13; return ans; break; }case 17:{ k2;k14;k15; return ans; break; }case 18:{ k7;k8;k18; return ans; break; } } return ans; }}int main(){ /*freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);*/ scanf("%d",&n); for(int i=0;i<3;i++){ for(int j=0;j<n;j++){ scanf("%I64d",&geo[j][i]); } } INF=2; for(int i=0;i<17;i++)INF*=10; LL ans=-INF; int pos=-1; k1;k10;k12;k13; printf("%I64d",ans); return 0;}上面的那堆亂亂的東西，其實是一個狀態表（而且很好看），只是博客寬度太短，裝不下
別的。。。也沒什么了
新聞熱點
疑難解答
