关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年2月13日
初学DP(5) – 棋盘型DP – NOIP 2000 提高组 第四题 方格取数 & POJ 2948 Martian Mining

棋盘型DP

棋盘型DP,是DP中比较坑的一种,大多数都可以用深搜AC拿上部分分,剩下的tle2333

所以这个就需要DP,通常我们是从左上朝右下找,当然了,棋盘DP却常常有种暴力的感觉

方格取数

题目链接: [http://codevs.cn/problem/1043/]

输入的方法很简单,也并没有什么复杂的预处理

对于这样一个棋盘,我们很容易想到他的阶段:从 f(i,j) 到 f(k,l) 的最优解

很明显这里已经不能用区间DP了,我们需要对 i j k l 进行枚举,另外,我们很容易发现,要是值最大,两条路径不应重合

针对与 f[i][j][k][l] 他是由两个坐标所组成的,所以我们就要分别考虑第一个坐标与第二个坐标的变化,每个坐标都有两种变化的可能,所以我们的状态转移方程应是:

f [ i ] [ j ] [ k ] [ q ] = max (
max ( f [ i – 1 ] [ j ] [ k – 1 ] [ q ] , f [ i ] [ j – 1 ] [ k ] [ q – 1 ] ) ,
max ( f [ i ] [ j – 1 ] [ k – 1 ] [ q ] , f [ i – 1 ] [ j ] [ k ] [ q – 1 ] ) )
+a [ k ] [ q ] + a [ i ] [ j ]

经过了这一步,我们就可以得到代码:

代码


#include <iostream>
#include <cstdio>
using namespace std;

int n,x,y,c;// 读入用
int a[20][20],f[20][20][20][20];//a[][] 存图 f[][] 动归

int main(){
// 读入
    scanf("%d",&n);
// 并不知道有多少组,那就无限输入吧
    while(1){
        scanf("%d%d%d",&x,&y,&c);
        if(x==0&&y==0&&c==0) break;// 全是 0 就该出来了
        a[x][y]=c;
    }
// 枚举
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                for(int q=1;q<=n;q++){
                    f[i][j][k][q]=max(max(f[i-1][j][k-1][q],f[i][j-1][k][q-1]),max(f[i][j-1][k-1][q],f[i-1][j][k][q-1]))+a[k][q]+a[i][j];//进行决策
                    if(i==k&&j==q) f[i][j][k][q]-=a[i][j];//如果两点相同,去掉重复的
                }
            }
        }   
    }
// 输出
    printf("%d",f[n][n][n][n]);
}

Martian Mining

题目链接: [http://poj.org/problem?id=2948]

翻译


本人才疏学浅,无法做到完全翻译,所以我只会翻译题干,如果有不明确之处请指出

火星上有一个被分为n*m个格子的矿区,每格子中有两种矿石,在北边有一个厂子炼一种矿,西边也有一个厂子炼另一种矿,现在有两种传送带-自南向北与自东向西,并且一个格子上只能安一种,传送带还不能转弯. 如果矿石没有被送进它所属的厂子,就是废石,现在,问你最多能采多少矿

题目


第一眼过去dfs+记忆化搜索

可是确实可以通过这个推出来

我们在进行搜索时,从右下往左上搜。搜到最优解,然后保存下来,于是我们可以翻过来,从左上到右下然,找出每一段的最优解,然后相加,ok!

通过这个问题我们应当把每一种矿石的 i – j 的区域有多少存下来,让后我们可以得出 dp 方程

f [ i ] [ j ] = max ( f [ i – 1 ] [ j ] + yr [ i ] [ j ] , f [ i ] [ j – 1 ] + bl [ i ] [ j ] )

其中 f[][] 为动归用数组 yr[i][j] 与 bl[i][j] 都是一种矿石从第 i 个格子到第 j 个格子的对应矿石个数

End


textsms