NOIP2008 提高组 C - 传纸条

上周的队内练习学弟选了这题来做~~当时纠结了很久也没搞出来...一个纸条传下去很好做~~但是两个纸条我当时就是没想通如何来避免后效性..

这道题的DP思想关键就是找到能表示出来的唯一状态...用一个三维数组就行了...因为纸条只能沿着斜线方向来传递..那么用dp [ k ] [ i ] [ j ] 表示从(1,1)出发的两个线路除起点没有公共点到达了第k号斜线的i与j能取得的最大值...只要状态找出来了..状态转移就简单了..更新dp [ k ] [ i ] [ j ] 无非就是4种情况来更新找到存在的并且最大的一直做到下面去就可以了..

刚还看了下Byvoid大牛的解题报告~~用的是高端洋气的最小费用流~~惭愧的是我几个月前就写过最大流了却一直没去继续深入~~~网络流还是很重要的~~要花时间来搞!

Program:

#include<iostream>
using namespace std;
int m,n,i,j,k,s[101][101],dp[101][101][101],ans;
int main()
{
     freopen("input.txt","r",stdin);
     freopen("P.out","w",stdout);
     while (~scanf("%d%d",&m,&n))
     {
           for (i=1;i<=m;i++)
              for (j=1;j<=n;j++) scanf("%d",&s[i][j]);      
           memset(dp,0,sizeof(dp)); 
           dp[3][1][2]=s[2][1]+s[1][2];
           for (k=4;k<m+n;k++)
           { 
                 for (i=1;i<k;i++)  
                 if (k-i<=m)
                 { 
                       for (j=i+1;j<k;j++)
                       if (k-j<=m)
                       {      
                              if (i!=1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j-1]);
                              if (i!=1 && j!=k-1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i-1][j]);
                              if (j-i!=1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j-1]);
                              if (j!=k-1) dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]); 
                              dp[k][i][j]+=s[k-i][i]+s[k-j][j];
                       }
                 }
           }
           if (m==1 || n==1) ans=0;
           else ans=dp[m+n-1][n-1][n];
           printf("%d\n",ans); 
     } 
     return 0;   
}