liangpeiqi0

pmax

题目大意：

有一个50*50的数字矩阵，你从左下角出发，每次可以向上或向右走一步，直到走到右上角。所有走过的路上的数值的积%107为你的得分，问你最大可以得多少分？

解题思路：

    这道题不能只求一个最大值，因为你不知道它乘上下一个数模107一定也是最大的。所以可以状态拆分，拆成107种，分别是余数为0到余数为106的。这样就变简单很多了。每次看看(i,j)的余数c可以到哪里。最后看终点的余数最大是多少。

参考程序：

# include <iostream>

# include <stdio.h>

# include <string.h>

using namespace std;

int a[55][55];

bool f[55][55][107];

int main()

{

       int n;

       cin>>n;

       memset(f,false,sizeof f);

       for (int i=1; i<=n; i++)

           for (int j=1; j<=n; j++) { cin>>a[i][j]; a[i][j]=a[i][j]%107; }

       f[n][1][a[n][1]]=true;  // 初始化

       for (int i=n; i>=1; i--)

           for (int j=1; j<=n; j++)

           if (i!=n || j!=1)

              {

                     for (int c=0; c<=106; c++)

                         if ( (i<50 && f[i+1][j][c]) || (j>1 && f[i][j-1][c]) )

                                f[i][j][(c*a[i][j])%107]=true;

              } // 动态规划

       for (int i=106; i>=0; i--)

           if (f[1][n][i]) { cout<<i<<endl; break; } // 求最大值

       return 0;

}