[NOIP 2008 提高组] 传纸条

知识点

多路径动态规划、网格路径、状态压缩

解题思路

把回程反向，看成两人同时从左上走到右下。两人走相同步数时只保存各自行号，列号由步数减行号确定；枚举两人上一步各自向右或向下。除起终点外不许重合。

正确性说明

每对互不共用同学的往返路径，反转回程后与一对同步单调路径一一对应。步数相同的状态覆盖全部位置组合，四种前驱穷尽移动选择；禁止中途相同位置确保每位同学只帮一次。按步数归纳，最大转移即最优好感度。

易错点

不能允许中间重合后只算一次分数；不可达状态必须负无穷；起终点允许相同且权为0。

复杂度

时间O((m+n)m²)，空间O(m²)，m,n≤50。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int m,n;cin>>m>>n;vector<vector<int>>a(m+1,vector<int>(n+1));for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)cin>>a[i][j];const int NEG=-1000000000;vector<vector<int>>dp(m+1,vector<int>(m+1,NEG));dp[1][1]=0;for(int s=3;s<=m+n;s++){auto nd=vector<vector<int>>(m+1,vector<int>(m+1,NEG));for(int x=1;x<=m;x++)for(int y=1;y<=m;y++){int c=s-x,d=s-y;if(c<1||c>n||d<1||d>n||(x==y&&s!=m+n))continue;int best=NEG;for(int u=0;u<=1;u++)for(int v=0;v<=1;v++)if(x-u>=1&&y-v>=1)best=max(best,dp[x-u][y-v]);if(best>NEG)nd[x][y]=best+a[x][c]+(x==y?0:a[y][d]);}dp.swap(nd);}cout<<dp[m][m]<<'\n';}