设为首页 加入收藏

TOP

HDU - 1003 - Max Sum && POJ - 1050 - To the Max （经典DP问题）
2015-11-21 01:02:53 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 1003 Max Sum POJ 1050 the 经典 问题

?

题目传送：HDU - 1003

?

思路：最大子序列和

dp[i]= a[i] (dp[i-1]<0)

dp[i]= dp[i-1]+a[i] (dp[i-1]>=0)

?

AC代码：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #define LL long long #define INF 0x7fffffff using namespace std; int n; int main() { int T; int cas = 1; scanf("%d", &T); while(T --) { scanf("%d", &n); int sum = 0; int ans = -INF; int from, to; int qi = 1, zhong = 1; for(int i = 1; i <= n; i ++) { int t; scanf("%d", &t); sum += t; zhong = i; if(sum > ans) { ans = sum; from = qi; to = zhong; } if(sum < 0) { qi = i + 1; sum = 0; } } printf("Case %d:\n%d %d %d\n", cas ++, ans, from, to); if(T != 0) printf("\n"); } return 0; }


?

?

题目传送：POJ - 1050

?

思路：最大子矩阵和，原理和上面那个题一样，就是把i~j行的列上的数加到一行去，再算该行的最大子序列和即可（0<=i<=j

?

AC代码：

?

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include
            #include 
            
              #include 
             
               #include 
              
                #define LL long long #define INF 0x7fffffff using namespace std; int a[105][105]; int tmp[105]; int n; int fun() { int max = -1, sum = 0; for(int i = 0; i < n; i ++) { sum += tmp[i]; if(sum > max) max = sum; if(sum < 0) sum = 0; } return max; } int main() { while(scanf("%d", &n) != EOF) { for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { scanf("%d", &a[i][j]); } } int ans = -1; for(int i = 0; i < n; i ++) { memset(tmp, 0, sizeof(tmp)); for(int j = i; j < n; j ++) { for(int k = 0; k < n; k ++) { tmp[k] += a[j][k]; } int t = fun(); if(ans < t) ans = t; } } cout << ans << endl; } return 0; }


?

?

?

?

?

?

?

?

?

?

?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：hdu 1506 Largest Rectangle in a.. 下一篇：poj1258 Agri-Net +hdu 1233 还是..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: