XTU -1231 人生成就 (dp + 记录最优解的个数）

http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1231

直接递推。

在保存最大值的时候同时保存有多少条到达最大值的路径，注意第一行第一列的情况即可。

别忘了取模。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 const int maxn = 510;
 6 int dp[maxn][maxn],p[maxn][maxn],q[maxn][maxn];
 7 int main()
 8 {
 9     int n;
10     while(~scanf("%d",&n))
11     {
12         memset(dp,0,sizeof(dp));
13         for(int i=1;i<=n;i++) {
14             for(int j=1;j<=n;j++) {
15                 scanf("%d",&p[i][j]);
16                 q[i][j]=1;
17             }
18         }
19         for(int i=1;i<=n;i++) {
20             for(int j=1;j<=n;j++) {
21                 if(dp[i-1][j]>dp[i][j-1]) {
22                     dp[i][j]=dp[i-1][j]+p[i][j];
23                     if(i==1||j==1) continue;
24                     q[i][j]=q[i-1][j];
25                 }
26                 else if(dp[i][j-1]>dp[i-1][j]) {
27                     dp[i][j]=dp[i][j-1]+p[i][j];
28                     if(i==1||j==1) continue;
29                     q[i][j]=q[i][j-1];
30                 }
31                 else {
32                     dp[i][j]=dp[i-1][j]+p[i][j];
33                     if(i==1||j==1) continue;
34                     q[i][j]=q[i-1][j]+q[i][j-1];
35                 }
36                 q[i][j]%=123456;
37             }
38         }
39     //    for(int i=1;i<=n;i++) {
40           //  for(int j=1;j<=n;j++)
41              //   printf("%d ",q[i][j]);
42            // printf("
");
43         //}
44         printf("%d
",q[n][n]%123456);
45     }
46     return 0;
47 }

View Code