首页 > 代码库 > codevs1169传纸条 不相交路径取最大，四维转三维DP
codevs1169传纸条 不相交路径取最大，四维转三维DP
这个题一个耿直的思路肯定是先模拟。。
但是我们马上发现这是具有后效性的。。也就是一个从(1,1)开始走，一个从(n,m)开始走的话
这样在相同的时间点我们就没法判断两个路径是否是相交的
于是在dp写挂了之后。。我们妥妥写了一发爆搜。。vis的那种
一旦你用了vis数组之后。。我们就不能再记忆化搜索了。。因为你缺少记录vis数组的状态。。
去了记忆化。。来了发纯爆搜。。果然T了。。但是在codevs上还得了30分。。不错不错。。
不错个锤子，ACM就是TLE
贴TLE代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int n,m; int a[55][55]; int dp[55][55][55][55]; bool vis[55][55]; const int INF=(~0u)>>2; bool check(int x,int y){ if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]) return true; return false; } int dfs(int x1,int y1,int x2,int y2,int dep){ // printf("(%d,%d) (%d,%d) DEP:%d\n",x1,y1,x2,y2,dep); // if(dp[x1][y1][x2][y2]!=-1) if(vis[x1][y1]||vis[x2][y2]) return -INF;else return dp[x1][y1][x2][y2]; if(x1==x2&&y1==y2) return -INF; if(x1==n&&y1==m&&x2==1&&y2==1) return 0; int p=-INF; if(check(x1+1,y1)&&check(x2-1,y2)){vis[x1+1][y1]=vis[x2-1][y2]=true;p=max(p,dfs(x1+1,y1,x2-1,y2,dep+1));vis[x1+1][y1]=vis[x2-1][y2]=false;} if(check(x1+1,y1)&&check(x2,y2-1)){vis[x1+1][y1]=vis[x2][y2-1]=true;p=max(p,dfs(x1+1,y1,x2,y2-1,dep+1));vis[x1+1][y1]=vis[x2][y2-1]=false;} if(check(x1,y1+1)&&check(x2-1,y2)){vis[x1][y1+1]=vis[x2-1][y2]=true;p=max(p,dfs(x1,y1+1,x2-1,y2,dep+1));vis[x1][y1+1]=vis[x2-1][y2]=false;} if(check(x1,y1+1)&&check(x2,y2-1)){vis[x1][y1+1]=vis[x2][y2-1]=true;p=max(p,dfs(x1,y1+1,x2,y2-1,dep+1));vis[x1][y1+1]=vis[x2][y2-1]=false;} // printf("DP (%d,%d,%d,%d):%d\n",x1,y1,x2,y2,p+a[x1][y1]+a[x2][y2]); // printf("from (%d,%d,%d,%d),(%d,%d,%d,%d),(%d,%d,%d,%d),(%d,%d,%d,%d)\n",x1+1,y1,x2-1,y2,x1+1,y1,x2,y2-1,x1,y1+1,x2-1,y2,x1,y1+1,x2,y2-1); return dp[x1][y1][x2][y2]=p+a[x1][y1]+a[x2][y2]; } int main(){ scanf("%d%d",&n,&m); int i,j; for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%d",&a[i][j]); memset(dp,-1,sizeof(dp)); printf("%d\n",dfs(1,1,n,m,0)); return 0; }
我们有一个好办法。。那就是其实我们发现从两边搜到对角。。和从一边搜到对角即(1,1)=>(n,m)+(n,m)=>(1,1)==(1,1)=>(n,m)+(1,1)=>(n,m)
并且我们发现路程相同。。则速度也相同。。因为时间一样就妥妥的了。。
这样搜的话。。手画一下图就能发现。。我们在同一时刻就能判断相交了。。因为时间相同速度相同。。如果终点相同。。等于路程一定，速度不变
则时间是相同的。。
并且我们只需枚举x1,x2,step,因为起点固定在(1,1),则后面的点和起点的关系就是，(x1-1)+(y1-1)=step,即x1+y1=step+2
y1=step+2-x1;同理也有x2,y2
所以这样就能省下一维空间。。（这个感觉有点类似于数据库的范式惹，尽量少的元素决定主键。。主键生成的其他不算数。。
然后我们来贴一发代码
其中判定坐标不是（1,1）应该写成!(x==1&&y==1)或者写成(x!=1||y!=1),千万别丢掉括号！
贴上21ms代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int n,m; int a[55][55]; int dp[55][55][55]; const int INF=(~0u)>>2; bool check(int x,int y){ if(x>=1&&x<=n&&y>=1&&y<=m) return true; return false; } //相当于把两人放在同一起跑线生成到重点的不相交路线，这样判定相交就容易了很多，两头分别搜容易错开。。用过的后面会访问 //但是从同一点出发，因为速度是相同的，如果相交一定是同时在某一点相交（一定），容易想象不同点交错使用共同点的情况 //考虑到速度相同且起点相同。。仅仅枚举x1,x2就能得出各自的纵坐标，即(x-1)+(y-1)=sum,x+y=sum+2,则y=sum+2-x int dfs(int x1,int x2,int s){ int y1=s+2-x1,y2=s+2-x2; // printf("(%d,%d) (%d,%d) DEP:%d\n",x1,y1,x2,y2,dep); if(dp[x1][x2][s]!=-1) return dp[x1][x2][s]; if(!check(x1,y1)||!check(x2,y2)) { // printf("PASS BORDER\n"); return dp[x1][x2][s]=-INF; } if(s==n+m-2){ // printf("ENOUGH STEP\n"); if(x1==x2&&y1==y2&&x1==n&&y1==m) return dp[x1][x2][s]=0; return dp[x1][x2][s]=-INF; } if(x1==x2&&y1==y2&&(x1!=1||y1!=1)) {//判定特殊点搞错 // printf("JUDGE CROSS POINT\n"); if(x1==n&&y1==m) return dp[x1][x2][s]=0; return dp[x1][x2][s]=-INF; } int p=-INF; p=max(p,dfs(x1,x2,s+1)); p=max(p,dfs(x1+1,x2,s+1)); p=max(p,dfs(x1,x2+1,s+1)); p=max(p,dfs(x1+1,x2+1,s+1)); // printf("DP (%d,%d,%d,%d):%d\n",x1,y1,x2,y2,p+a[x1][y1]+a[x2][y2]); // printf("from (%d,%d,%d,%d),(%d,%d,%d,%d),(%d,%d,%d,%d),(%d,%d,%d,%d)\n",x1,s+3-x1,x2,s+3-x2,x1+1,s+3-x1-1,x2,s+3-x2,x1,s+3-x1,x2+1,s+3-x2-1,x1+1,s+3-x1-1,x2+1,s+3-x2-1); return dp[x1][x2][s]=p+a[x1][y1]+a[x2][y2]; } int main(){ scanf("%d%d",&n,&m); int i,j; for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%d",&a[i][j]); memset(dp,-1,sizeof(dp)); printf("%d\n",dfs(1,1,0)); return 0; }
codevs1169传纸条 不相交路径取最大，四维转三维DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。