棋盘型动态规划


洛谷P1004 方格取数

题意:N*N的网格图,有些格点上有数字,从左上角到右下角走两次,使得取得的数字总和最大(取走后格点数字为零)

分析:两次作为一次,即同时走,直接四层for循环,每次两个点[i,j]和[k,l]同时转移,然后再判断一下,[i,j]和[k,l]是否是同一个点,如果是同一个点,减去一个数字即可.

int a[10][10],f[10][10][10][10];
int main(){
    int n=read();
    while(1){
        int x=read(),y=read(),z=read();
        if(!x&&!y&&!z)break;
        a[x][y]=z;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
        for(int l=1;l<=n;l++){
            f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i][j-1][k-1][l],max(f[i-1][j][k][l-1],f[i][j-1][k][l-1])))+a[i][j]+a[k][l];
            if(i==k&&j==l)f[i][j][k][l]-=a[i][j];
        }
    printf("%d\n",f[n][n][n][n]);
    return 0;
}

洛谷P1006 传纸条

题意:m*n的矩阵,左上角和右下角的权值为零,从左上角走到右下角,再从右下角走到左上角,要求不能经过同一个点,求经过路径权值和最大值.

分析:首先就看作两次从左上角到右下角这个转化是没有问题的吧.然后接着考虑上题是走过一次之后权值为零,但还可以走;本题是走过一次之后不能再走了.但对于动态规划来说,这是没有区别的,为什么呢?因为上题中走过一次之后权值为零的点,第二次绝对不会再走了,因为动态规划处理的是最优性问题.

跟上面的代码一样

int a[51][51],f[51][51][51][51];
int main(){
    int m=read(),n=read();
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++){
        a[i][j]=read();
    }
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=m;k++)
        for(int l=1;l<=n;l++){
            f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])))+a[i][j]+a[k][l];
            if(i==k&&j==l)f[i][j][k][l]-=a[i][j];
        }
    printf("%d\n",f[m][n][m][n]);
    return 0;
}

有没有觉得开四维太不优秀了,我们来尝试滚掉一维.我们之前开四维是对于两次DP同时转移,其实不难发现既然两次DP是同时转移,那么它们走的步数时刻都是相同的.

于是我们可以第一维表示走了多少步,第二维和第三维分别枚举两次DP的行或者列,因为我们知道了步数和行,就能表示出列(或者知道步数和列,就能表示出行),我下面的代码是枚举的行.

int a[55][55],f[105][55][55];
//因为第一维枚举的是步数,所以数组第一维要m+n
int main(){
    int m=read(),n=read();
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        a[i][j]=read();
    for(int i=1;i<=m+n-1;i++)//枚举步数
    for(int j=1;j<=m;j++)//枚举第一次DP的行
    for(int k=1;k<=m;k++){//枚举第二次DP的行
        if(i-j+1<1||i-k+1<1)continue;
//判断列是否合法,不合法就跳过
        f[i][j][k]=max(f[i-1][j][k-1],max(f[i-1][j][k],max(f[i-1][j-1][k-1],f[i-1][j-1][k])))+a[j][i-j+1]+a[k][i-k+1];
        if(j==k)f[i][j][k]-=a[j][i-j+1];
//判断是否经过了同一个点
    }
    printf("%d\n",f[m+n-1][m][m]);
    return 0;
}
优质内容筛选与推荐>>
1、从Excel中读出导入sql server
2、假如生活欺骗了你!——Leo网上答疑(14)
3、一个有理数集上的实数集函数
4、详解keepalived配置和使用
5、关于typedef的用法总结


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号