首页 > 代码库 > POJ:1050(枚举 + DP)

POJ:1050(枚举 + DP)

 1 #include <stdio.h> 2 #include <math.h> 3 #include <iostream> 4 #include <string.h> 5 #include <algorithm> 6 using namespace std; 7 #define N 105 8 int f[N][N]; 9 int sum[N][N];10 int main(){11     int n;12     while(scanf("%d",&n)!=EOF){13         memset(f,0,sizeof(f));14         memset(sum,0,sizeof(sum));15         for(int i=1;i<=n;i++)16             for(int j=1;j<=n;j++)  scanf("%d",&f[i][j]);17         for(int i=1;i<=n;i++)18              for(int j=1;j<=n;j++){19                  if(j==1) sum[j][i] = f[j][i];20                  else sum[j][i] = f[j][i] + sum[j-1][i];  21              }        22         //n最大为100,这里就是简单的将枚举与dp结合起来: 23         //通过枚举从i行到j行, 计算列和之后,每一“行” 进行普通的最长连续子序列求和dp 24         int dp[N];25         int maxc = (int)-1e9;26         for(int i=1;i<=n;i++){27             for(int j=i;j<=n;j++){28                int num=0;29                memset(dp,0,sizeof(dp));30                dp[1] = sum[j][1]-sum[i-1][1];31                maxc = max(dp[1],maxc);32                for(int k=2;k<=n;k++){33                        if(dp[k-1] > 0) dp[k] = dp[k-1] + (sum[j][k]-sum[i-1][k]);34                        else dp[k] = sum[j][k]-sum[i-1][k];35                        maxc = max(dp[k],maxc);36                }37             }        38         } 39         printf("%d\n",maxc);     40     }41     return 0;   42 }

·注意看注释即可

POJ:1050(枚举 + DP)