Codeforces 762D. Maximum path
首先，这是一道DP题，虽然说有简便的做法，但我还是采用了插头DP的方法（不知道是不是插头DP，可能是轮廓线DP）
Problem
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.
Input
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
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.
Examples
Input
3
1 1 1
1 -1 1
1 1 1
Output
7
Input
5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10
Output
110
Note
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;
}上面的那堆乱乱的东西，其实是一个状态表（而且很好看），只是博客宽度太短，装不下
错点记录
- 对于define语句中的常量，不能过大，也不能作为返回值直接使用，因为这样会被强转为int型，要计算INF
别的。。。也没什么了
京公网安备 11010502036488号