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

最新文章

热门文章

巴特西

codevs1169传纸条 不相交路径取最大，四维转三维DP

最新文章

热门文章

codevs1169传纸条不相交路径取最大，四维转三维DP