【NOIP2008】传纸条题解(DP)

Source
版权声明:转载请注明原出处啦QAQ(虽然应该也没人转载): https://blog.csdn.net/hzk_cpp/article/details/86764319

这是一道dp题,当然也可以用网络流做.

题目:luogu1006.

题目大意:

棋盘的每个点有一个值 a i , j a_{i,j} ,现在要从左上角传到右下角,传两次,每次只能传到下方或右方一格,且两条路径不重叠,问走过路径上的 a i , j a_{i,j} 之和最大为多少.

那么这道题考虑dp(本人太蒟,不会网络流).

我们考虑最简单最暴力的dp状态, f [ i ] [ j ] [ k ] [ l ] f[i][j][k][l] 表示第一次传到了 ( i , j ) (i,j) 第二次传到了 ( k , l ) (k,l) 的最大值.

那么方程就是:
f [ i ] [ j ] [ k ] [ l ] = m a x ( f [ i 1 ] [ j ] [ k 1 ] [ l ] , f [ i 1 ] [ j ] [ k ] [ l 1 ] , f [ i ] [ j 1 ] [ k 1 ] [ l ] , f [ i ] [ j 1 ] [ k ] [ l 1 ] ) + a [ i ] [ j ] + a [ k ] [ l ] f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k-1][l],f[i][j-1][k][l-1])+a[i][j]+a[k][l]

然后我们就枚举,但是由于路径不可重复复,我们要注意如何保证答案正确且不重复.

可以保证,只要 i k i≠k j l j≠l ,就可以不重复.

那么代码如下:

#include<bits/stdc++.h>
  using namespace std;
#define rep(i,j,k) for (int i=j;i<=k;i++)
int n,m;
int a[51][51]={0};
int f[51][51][51][51]={0};
inline void into(){
  scanf("%d%d",&n,&m);
  rep(i,1,n)
    rep(j,1,m)
      scanf("%d",&a[i][j]);
}
inline void work(){
  rep(i,1,n)
    rep(j,1,m)
      rep(k,1,n)
        rep(l,1,m)
          if (i!=k||j!=l) 
            f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
  f[n][m][n][m]=max(f[n-1][m][n][m-1],f[n][m-1][n-1][m])+a[n][m];      //最后一步的特殊处理 
}
inline void outo(){
  printf("%d\n",f[n][m][n][m]);
}
int main(){
  for (int i=1;i<=1;i++){
    into();
    work();
    outo();
  }
  return 0;
}

好吧,这样还是可以优化的.

我们可以让每次传纸条时的状态同步.

也就是说第一次走到了 ( i , j ) (i,j) ,第二次走到了 ( k , l ) (k,l) ,那么两次的步数必须相等.

那么我们会发现 i + j = k + l = s t e p i+j=k+l=step (步数),所以我们的状态可以简化为 f [ i ] [ j ] [ k ] f[i][j][k] 表示走了 i i 步,第一次横坐标或纵坐标为 j j ,第二次横坐标或纵坐标为 k k 的最大值.

这里我们设两次都为纵坐标,那么:
f [ i ] [ j ] [ k ] = m a x ( f [ i 1 ] [ j ] [ k ] , f [ i 1 ] [ j 1 ] [ k ] , f [ i 1 ] [ j ] [ k 1 ] , f [ i 1 ] [ j 1 ] [ k 1 ] ) + a [ i j ] [ j ] + a [ i k ] [ k ] f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k],f[i-1][j][k-1],f[i-1][j-1][k-1])+a[i-j][j]+a[i-k][k]

所以代码如下:

#include<bits/stdc++.h>
  using namespace std;
#define rep(i,j,k) for (int i=j;i<=k;i++)
int n,m;
int a[51][51]={0};
int f[201][51][51]={0};
inline void into(){
  scanf("%d%d",&n,&m);
  rep(i,1,n)
    rep(j,1,m)
      scanf("%d",&a[i][j]);
}
inline void work(){
  f[2][1][1]=0;      //由于要走m+n-2步,所以初始直接从2开始 
  rep(i,3,m+n-1)      //由于最后一步要特殊处理,所以枚举到m+n-1
    rep(j,1,m)
	  rep(k,1,m)
	    if (i-j<=n&&i-k<=n&&i-j>=1&&i-k>=1&&j!=k) f[i][j][k]=max(max(f[i-1][j][k],f[i-1][j-1][k]),max(f[i-1][j][k-1],f[i-1][j-1][k-1]))+a[i-j][j]+a[i-k][k];
}
inline void outo(){
  printf("%d\n",max(f[m+n-1][m-1][m],f[m+n-1][m][m-1]));      //懒,直接输出 
}
int main(){
  for (int i=1;i<=1;i++){
    into();
    work();
    outo();
  }
  return 0;
}