HDU – 1003 – Max Sum && POJ – 1050 – To the Max (经典DP问题)

HDU – 1003 – Max Sum && POJ – 1050 – To the Max (经典DP问题)

HDU – 1003 – Max Sum && POJ – 1050 – To the Max (经典DP问题)

 

难题传送:HDU – 1003

 

HDU – 1003 – Max Sum && POJ – 1050 – To the Max (经典DP问题)。思路:最大子类别和

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钱柜999,~j行的列上的数加到生龙活虎行去,再算该行的最大子种类和即可(0<=i<=j
< strong=””><>

 

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;
}

 

 

 

 

 

 

 

 

 

 

 

 

– 1003 – 马克斯 Sum POJ – 1050 – To the Max(杰出DP难题卡塔尔国 标题传送:HDU – 1003 思路:最大子连串和 dp[i]= a[i]
(dp[i-1]0) dp[i]= dp[i-1]+a[i] (dp[i-1]=0) AC代码…

POJ 2593&&2479:Max Sequence

Max Sequence

Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 16329   Accepted: 6848

Description

Give you N integers a1, a2 … aN (|ai| <=1000, 1 <= i <= N).

钱柜999 1

 

You should output S.

 

Input

The input will consist of several test cases. For each test case, one
integer N (2 <= N <= 100000) is given in the first line. Second
line contains N integers. The input is terminated by a single line with
N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5-5 9 -5 11 200

Sample Output

40

题意是付诸一个类别,求那么些行列中八个子系列的和的最大值。
两五年前切了POJ2479,但当时还十分不清楚dp
(当然以往对dp的领会程度也就能够切切dp水题。。。)。所以做那道题的时候最棒感叹。
其实求贰个队列的和的最大值很粗大略,即dp[i]=max(dp[i-1]+value[i],
value[i])
以往它须求四个系列的和的最大值。所以想到从侧面来叁次,从右侧来二遍。
left[i]代表从第四个数字到如今第i个数字停止,左侧包车型大巴最大系列和。
right[i]意味着从第Test个数字(从右向左)到第i个数字甘休,左边的最大种类和。
代码:

#include 
#include 
#include 
using namespace std;

int left_v[100005];
int right_v[100005];
int value[100005];

int main()
{
 int Test;
 while(cin>>Test)
 {
  if(!Test)
   break;

  left_v[0]=0;
  right_v[0]=0;
  left_v[Test+1]=0;
  right_v[Test+1]=0;

  int i,max_v=-100000000;
  for(i=1;i<=Test;i++)
  {
   cin>>value[i];
  }
  left_v[1]=value[1];
  right_v[Test]=value[Test];

  for(i=2;i<=Test;i++)
  {
   left_v[i]=max(left_v[i-1]+value[i],value[i]);
  }
  for(i=Test-1;i>=1;i--)
  {
   right_v[i]=max(right_v[i+1]+value[i],value[i]);
  }
  for(i=2;i<=Test;i++)
  {
   left_v[i]=max(left_v[i-1],left_v[i]);
  }
  for(i=Test-1;i>=1;i--)
  {
   right_v[i]=max(right_v[i+1],right_v[i]);
  }
  for(i=1;imax_v)
    max_v=left_v[i]+right_v[i+1];
  }
  cout<<

自己把这道题A掉,相当开心。2015/7/5。

 <

25932479:Max Sequence Max Sequence Time
Limit: 3000MS Memory Limit: 65536K Total Submissions: 16329 Accepted:
6848 Description Give you N integers a1, a2 … aN (|ai|
=1000,…

题目:

主题材料链接:

AC代码:

 # include <stdio.h>
 int a[100010];
 int main ()
 {
     int t,n,ret,sum,max,i,sta,end,flag=1;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%d",&n);
         for(i=0;i<n;i++)
             scanf("%d",&a[i]);
         sta=0; end=0; ret=0;
         max=a[0]; sum=a[0];
         for(i=1;i<n;i++)
         {
             if(sum+a[i]<a[i])
             {
                 ret=i;
                 sum=a[i];
            }
            else 
                sum+=a[i];

            if(max<sum)
            {
                max=sum;
                sta=ret;
                end=i;
            }
        }

        printf("Case %d:\n",flag);
        printf("%d %d %d\n",max,++sta,++end);
        flag++;
        if(t)
            printf("\n");
    }
 }
admin

网站地图xml地图