标签：棋盘型dp

棋盘型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*ｍ个格子的矿区，每格子中有两种矿石，在北边有一个厂子炼一种矿，西边也有一个厂子炼另一种矿，现在有两种传送带-自南向北与自东向西，并且一个格子上只能安一种，传送带还不能转弯. 如果矿石没有被送进它所属的厂子，就是废石，现在，问你最多能采多少矿

题目

---

第一眼过去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

]]>