OI

【动态规划】T4方格取数

先从动规刷起 ,做了这么一道题，2000年的老题，提高组第四题

题目直接限制了只能向下或向右走，换句话说就是每个点只能由上或由左走到。因此，如果只考虑一条路径，还是比较直观就能想明白：

设F[i][j]表示走到i行j列时的最大值

则F[i][j]=max{F[i-1][j],F[i][j-1]} +a[i][j]//F[i][j]只能由这两格转移来

只考虑一条路径就可以这么写：

1
2
3
4
for(i=1;i<=n;i++)  
  for(j=1;j<=n;j++)  
    if(f[i-1][j]>f[i][j-1])f[i][j]=f[i-1][j]+map[i][j];  
    else f[i][j]=f[i][j-1]+map[i][j];

虽然，题目要求又多了一条路径，但是如果沿着这个思路，也就不难想了，只是需要四维数组，分别记下两条路径。而下一个状态，应该是以四种状态中的最大值转移得来。由于题目限制n<=10，于是就可以不用犹豫使用这样的四种循环动规求解了，列出动态转移方程：
设F[i][j][k][l]表示第一条路径走到i行j列，第二条路径走到k行l列时的最大值

则F[i][j][k][l]=max{F[i-1][j][k-1][l],F[i][j-1][k-1][l],F[i-1][j][k][l-1],F[i][j-1][k][l-1]}+a[i][j]+a[k][l]

//分别是第一条路径的两种和第二条路径的两种，乘法原理

因此，最后的写法就是个四重循环O(n^4)//n<=10

1
2
3
4
5
6
7
8
for(i=1;i<=n;i++)  
  for(j=1;j<=n;j++)  
    for(k=1;k<=n;k++)  
      for(l=1;l<=n;l++){  
        f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i][j-1][k-1][l],  
        f[i-1][j][k][l-1],f[i][j-1][k][l-1])+map[i][j]+map[k][l];  
        if(i==k&&j==l)f[i][j][k][l]-=map[i][j];  
      }

这里还有一个容易忽视的细节，i,j,k,l重合时，a[i][j]只能被加一次//边界条件

这题尽管不是很难理解，但利用了n<=10这一条件，用四维数组DP的做法还是很巧妙。

居然还有四维压三维的做法

之前的F[i][j][k][l]四维做法，会发现有许多冗余计算：对于每一组路径上各取一点的所有组合都会被重复计算。

我们可以发现因为只能向下或向右，两条路径的长度是确定的，而设共走了k步（以左上角为第一步），对于每一个k，点(i,j)的坐标都有i=k-j+1，因此就可以以一个k代替原来的两个横坐标（或纵坐标）。

于是可以进行三维的优化：

设F[i][j][k]表示第一条路径走到第i列，第二条路径走到第j列，共走了k步时的最大值

这样，动态转移方程就是：

F[i][j][k]=max(F[i-1][j][k-1],F[i][j-1][k-1],F[i][j][k-1],F[i-1][j-1][k-1])+a[i][k-i+1]+a[j][k-j+1]

//F[i][j][k]由上一步k-1的四个点的最大值转移，四个点与四维做法相同

还有一点是，由于记录的是步数，对应步数下的i,j取值范围改变，应为[1,k] (k<=n),[k-n+1,n] (k>n)

所以，最后的代码O(n^3)：

1
2
3
4
5
6
7
8
9
f[1][1][1]=map[1][1];  
for(k=2;k<=2*n-1;k++)  
  for(i=max(1,k-n+1);i<=min(n,k);i++)  
    for(j=max(1,k-n+1);j<=min(n,k);j++){  
      f[i][j][k]=max(max(f[i-1][j][k-1],f[i][j-1][k-1]),  
      max(f[i][j][k-1],f[i-1][j-1][k-1]))+map[i][k-i+1]+map[j][k-j+1];  
      if(i==j)f[i][j][k]-=map[i][k-i+1];  
    }  
printf("%d",f[n][n][2*n-1]);

、、、
这就很妙了(￣▽￣)~*