AcWing 1027. 方格取数·为甚么不能分开走

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1027. 方格取数·为甚么不能分开走原题链接简单

作者：

yuyangp , 2020-07-07 17:18:02 , 所有人可见 , 阅读 5046

66

23

为什么不能分开走

分开两次走（贪心）：第一次走到(n, n)求出最大值并记录路径令路径上点收益为0后再走一次。

第一次走为局部最优并且也对第二次走造成了影响，第二次走是在第一次影响下所能走的局部最优，不具备“无后效性”，因此分开两次走并不是全局最优解

算法一：

同时走：分别从(1,1)(1,1)出发走到终点(n, n)(n, n)

同时走两条路径，令(i1,j1),(i2,j2)分别表示两条路径所经过的点
dp[i1][j1][i2][j2] 表示所有从(1,1)(1,1)走到(i1,j1)(i2,j2)路径的最大值
当i1 == i2 && j1 == j2时代表两条路径出现重复点，则只取一次a[i1][j1]的值

闫式DP分析法

观察可发现，当两条路径走的步长相同时，才有可能出现重复点

而我们所求中，对结果造成干扰的特殊情况正是‘出现重复点’，我们可以只考虑同时走（二者同时走一步）

优化一下可发现，因为每步同时走 i1 + j1 == i2 + j2 必然成立
可令k = i1 + j1
则dp[i1][j1][i2][j2] 可转化为 dp[k][i1][i2]

算法二：

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int n;
int a[N][N];
int dp[N << 1][N][N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    int x, y, z;
    while (cin >> x >> y >> z, x || y || z) a[x][y] = z;
    for (int k = 2; k <= n << 1; ++ k)  {
        for (int i1 = 1; i1 <= n; ++ i1) {
            int j1 = k - i1;
            if (j1 < 1 || j1 > n) continue;
            for (int i2 = 1; i2 <= n; ++ i2) {
                int j2 = k - i2;
                if (j2 < 1 || j2 > n) continue;
                int &x = dp[k][i1][i2];
                x = dp[k - 1][i1][i2];
                x = max(x, dp[k - 1][i1 - 1][i2]);
                x = max(x, dp[k - 1][i1][i2 - 1]);
                x = max(x, dp[k - 1][i1 - 1][i2 - 1]);
                x += a[i1][j1];
                if (i1 != i2) x += a[i2][j2];
            }
        }
    }

    cout << dp[n << 1][n][n] << "\n";

    return 0;
}

19 评论

天郁闷 2022-01-17 18:22

因为第一次走的时候有可能有好几条路径都是第一次的解，而你分开走只能选择其中的一条。很不幸的是，第一次走过的地方会被重置成0，而你不确定的是第一次同样是最优解而未被你选择的情况下第二次的值会不会比你已经得出的答案要大。

12312123 2022-03-21 19:37

爹！

毛毛毛 2022-04-15 16:26

爹！

无名之辈又帅了嗷 2022-06-27 10:30

牛蛙

MongoRolls 2022-07-02 16:35

牛蛙

GXNUsuanfatigao01 2022-07-31 14:01

tql

淞筱 2022-10-18 20:12

卧槽，解决了我的困惑，爹！

讲究 2022-10-25 12:20 回复了 12312123 的评论

开怀大孝

12312123 2022-10-26 10:48 回复了讲究的评论

好好孝

WA-TLE 2022-10-28 10:07

tql

普通朋友 2023-03-18 11:40

大佬，第一次同样是最优解而未被你选择的情况下第二次的值会不会比你已经得出的答案要大。这句话具体是什么意思呢，还是不太懂

指尖上的的青春 2023-04-04 23:53

牛逼

lkp1189 2023-04-28 22:41

爹！

魔法恐龙 2023-07-10 14:36

退役账户 10个月前

0 0 3 0
3 0 0 0
0 0 0 2
2 0 0 0

kafuuaki 10个月前

或许题目应该说清楚到底应该同时走还是分开走, A到B走两次看起来就很像分开走

ghost_him 2023-01-28 21:15

如果一个路径向右，一个路径向下，如果当前的状态x1 - x2 = 1，转移过来的路径不会重合嘛

静夜@ 2022-03-28 21:09

# include <iostream>
# include <cmath>
# include <algorithm>
# include <bits/stdc++.h>
int a[1005][1005],dp[11][11][11][11]; 
using namespace std;
int main()
{
    int n;int x,y,z;
    n=11;
    cin>>n;
     while(1)
     {
        cin>>x>>y>>z;
        if(x==0&&y==0&&z==0) 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++)
      {int temp;
      if(i==l&&j==k)
            temp=a[i][j];        
     else
         temp=a[i][j]+a[k][l];
        dp[i][j][k][l]=max(dp[i-1][j][l][k-1],dp[i][j][l][k]);
        dp[i][j][k][l]=max(dp[i-1][j][l-1][k],dp[i][j][l][k]);
        dp[i][j][k][l]=max(dp[i][j-1][l-1][k],dp[i][j][l][k]);
        dp[i][j][k][l]=max(dp[i][j-1][l][k-1],dp[i][j][l][k]);
        dp[i][j][k][l]+=temp;
      }
  cout<<dp[n][n][n][n]<<endl;
 }

这样是因为枚举两个终点，无法记录某些数字已取所以导致重复吗？那为什么枚举路径长度就行呢?后面不一样用了枚举两个终点吗？怎么就没重复了呢？不也没标记吗？

梦是回忆 2022-05-01 21:00

{
int temp;
if(i==k&&j==l)
temp=a[i][j];
else
temp=a[i][j]+a[k][l];
dp[i][j][k][l]=max(dp[i-1][j][k-1][l]+temp,dp[i][j][k][l]);
dp[i][j][k][l]=max(dp[i-1][j][k][l-1]+temp,dp[i][j][k][l]);
dp[i][j][k][l]=max(dp[i][j-1][k][l-1]+temp,dp[i][j][k][l]);
dp[i][j][k][l]=max(dp[i][j-1][k-1][l]+temp,dp[i][j][k][l]);
}
中间这样写，可以过的