hdu 1003 Max Sum(动态规划)

解题思路：

本题在给定的集合中找到最大的子集合【子集合：集合的元素的总和，是所有子集合中的最大解。】

结果输出：最大的子集合的所有元素的和，子集合在集合中的范围区间.

依次对元素相加，存到一个 sum 中,同时ans=sum;定义左右边界 left,right;临时左边界ll=1;

如果sum>ans，则ans=sum; 左边界 left=tem; right=i+1;

如果sum<0,则sum=0; tem=i+2;

Ac code:

 #include<bits/stdc++.h>

 using namespace std;

 int main()

 {

     int t,a,sum,ans,l,r,x,ll;

     scanf("%d",&t);

     for(int k=; k<=t; k++)

     {

         sum=;ans=-;ll=;

         scanf("%d",&x);

         for(int i=; i<x; i++)

         {

             scanf("%d",&a);sum+=a;

             if(sum>ans)

             {ans=sum;l=ll;r=i+;}

             if(sum<)

             {sum=;ll=i+;}

         }

         printf("Case %d:\n%d %d %d\n",k,ans,l,r);

         if(k!=t)printf("\n");

     }

     return ;

 }

简单DP: 2017.03.29

 #include<stdio.h>

 #include<algorithm>

 #include<string.h>

 using namespace std;

 #define N 100005

 int dp[N];

 int a[N];

 int main()

 {

     int t;

     while(scanf("%d",&t)!=EOF)

     {

         int c=,T=t;

         while(t--)

         {

             memset(dp,,N);

             int n;

             scanf("%d",&n);

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

                 scanf("%d",&a[i]);

             dp[]=a[];

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

                 dp[j]=max(dp[j-]+a[j],a[j]);

             int mx=-;

             int st=,en=;

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

                 if(mx<dp[i])

                 {

                     mx=dp[i];

                     en=i;

                 }

             st=en;

             int sum=;

             for(int i=en; i>=; i--)

             {

                 sum+=a[i];

                 if(sum==mx)

                     st=i;

             }

             printf("Case %d:\n%d %d %d\n",c,mx,st,en);

             if(c!=T)printf("\n");

             c+=;

         }

     }

     return ;

 }

巴特西

hdu 1003 Max Sum(动态规划)

最新文章

热门文章