洛谷P1004 方格取数动态规划多维DP

题目描述

设有N×N的方格图(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。如下图所示（见样例）:

A 0  0  0  0  0  0  0  0 0  0 13  0  0  6  0  0 0  0  0  0  7  0  0  0 0  0  0 14  0  0  0  0 0 21  0  0  0  4  0  0 0  0 15  0  0  0  0  0 0 14  0  0  0  0  0  0 0  0  0  0  0  0  0  0                         B

某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入格式

输入的第一行为一个整数N（表示N×N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输出格式

只需输出一个整数，表示2条路径上取得的最大的和。

输入输出样例

输入 #1复制

82 3 132 6  63 5  74 4 145 2 215 6  46 3 157 2 140 0  0

输出 #1复制

说明/提示

NOIP 2000 提高组第四题

Solution

这道题最初我还以为可以使用贪心，两遍dfs……

但是会有一些特殊情况

比如：

0　　1　　1

3　　3　　3

1　　1　　0

若用贪心，第一条路应该是“0　　3　　3　　3　　0”=9

第二条路是“0　　1　　1　　0　　0”=2

总和为11

但是如果第一次走“0　　1　　3　　3　　0”=7

第二条路走“0　　3　　1　　1　　0”=5

总和为12

好了，这种贪心已经被证明是错误的了

Algorithm1

四维DP

由于两条路径的长度是相同的

又为了满足DP的“递推规则”

我在这里设前两维表示第一条路已经走到了第i行第j列

后两维表示第二条路已经走到了第k行第l列

那么DP[i][j][k][l]=四周DP的最大值+当前两条路走到的格子的价值

如果i==k并且k===l

说明这两条路走到了一起

所以这时只要计算一遍这一格的价值。

Code1

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
           7 #include
           
             8 #include
            
              9 #include
             
              10 #define IL inline11 #define re register12 using namespace std;13 14 IL int read()15 {16 re int res=0;17 re char ch=getchar();18 while(ch<'0'||ch>'9')19 ch=getchar();20 while(ch>='0'&&ch<='9')21 res=(res<<1)+(res<<3)+(ch^48),ch=getchar();22 return res;23 }24 int n;25 int f[10][10];26 int dp[10][10][10][10];27 int main()28 {29 n=read();30 int tx=read(),ty=read(),tz=read();31 while(tx!=0||ty!=0||tz!=0)32 {33 f[tx][ty]=tz;34 cin>>tx;35 cin>>ty;36 cin>>tz;37 }38 for(int i=1;i<=n;i++)39 for(int j=1;j<=n;j++)40 for(int k=1;k<=n;k++)41 for(int l=1;l<=n;l++)42 {43 int now=0;44 now=max(now,dp[i-1][j][k][l-1]+f[i][j]+f[k][l]);45 now=max(now,dp[i][j-1][k][l-1]+f[i][j]+f[k][l]);46 now=max(now,dp[i-1][j][k-1][l]+f[i][j]+f[k][l]);47 now=max(now,dp[i][j-1][k-1][l]+f[i][j]+f[k][l]);48 if(i==k&&j==l) now-=f[i][j];49 dp[i][j][k][l]=now;50 }51 cout<

Algorithm2

事实上，我们可以发现

由于两条路是同时走的

所以当前的格子与起点（终点）的曼哈顿距离是相同的

即

$$i+j==k+l$$

那不就可以省去l了嘛，通过i，j，k就可以计算出相对应的合法的l！

Code2

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
           7 #include
           
             8 #include
            
              9 #include
             
              10 #define IL inline11 #define re register12 using namespace std;13 14 IL int read()15 {16 re int res=0;17 re char ch=getchar();18 while(ch<'0'||ch>'9')19 ch=getchar();20 while(ch>='0'&&ch<='9')21 res=(res<<1)+(res<<3)+(ch^48),ch=getchar();22 return res;23 }24 int n;25 int f[10][10];26 int dp[10][10][10];27 int main()28 {29 n=read();30 int tx=read(),ty=read(),tz=read();31 while(tx!=0||ty!=0||tz!=0)32 {33 f[tx][ty]=tz;34 cin>>tx;35 cin>>ty;36 cin>>tz;37 }38 for(int i=1;i<=n;i++)39 for(int j=1;j<=n;j++)40 for(int k=1;k<=n&&i+j-k>0;k++)41 {42 int now=0;43 now=max(now,dp[i-1][j][k]+f[i][j]+f[k][i+j-k]);44 now=max(now,dp[i][j-1][k]+f[i][j]+f[k][i+j-k]);45 now=max(now,dp[i-1][j][k-1]+f[i][j]+f[k][i+j-k]);46 now=max(now,dp[i][j-1][k-1]+f[i][j]+f[k][i+j-k]);47 if(i==k) now-=f[k][i+j-k];48 dp[i][j][k]=now;49 }50 cout<