早昨晚，跪，体倦。简直太CF该，早上起来刷标题！Then,书写python，shell,一天后基础。

标题或标题中国～！

思考：它似乎已经开始了这个话题dfs，但是，这个矩阵外观似太大，dfs不碰，老实实dp吧。我的做法是。先刷掉最第一列，由于第一列仅仅能从左上往下。then,第i行第j列应该就是dp[i][j]=max(dp[i-1][j],dp[i][k] )+dp[i][j],(k为j的真因子)。我在找因子时候全然没优化，没什么必要，懒得写～

ACcode

/***********************************************************	> OS     : Linux 3.2.0-60-generic #91-Ubuntu	> Author : yaolong	> Mail   : dengyaolong@yeah.net 	> Time   : 2014年05月31日 星期六 07:45:21 **********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int dp[30][1234];int main(){    int T,n,m;    scanf("%d",&T);    while(T--){        scanf("%d%d",&n,&m);        int i,j,tmp,k;        for( i=1;i<=n;i++){            for( j=1;j<=m;j++){                scanf("%d",&dp[i][j]);            }        }        for( i=2;i<=n;i++){            dp[i][1]+=dp[i-1][1];        }        for( i=1;i<=n;i++){            for( j=2;j<=m;j++){                 tmp=dp[i][j-1];                 k=1;                for(;k
         
          1) tmp=max(dp[i-1][j],tmp);            dp[i][j]+=tmp;            }        }        printf("%d\n",dp[n][m]);    }    return 0;}
         
        
       
      
     

版权声明：本文博主原创文章。博客，未经同意不得转载。