首页 > 代码库 > HDU_1003Max Sum 简单动归

HDU_1003Max Sum 简单动归

2024-07-30 23:17:44   225人阅读

以前做过这道题目，那是还不懂状态方程。乱搞一气：

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=5000+10; 5 int a[maxn]; 6 int main() 7 { 8     int  T; 9     scanf("%d",&T);10     for(int i=1;i<=T;i++)11     {12         int n;13         scanf("%d",&n);14         for(int j=0;j<n;j++)15             scanf("%d",&a[j]);16         int maxd=a[0];17         int temp=a[0];18         int left=0;19         int right=0;20         int x=0;21         for(int j=1;j<n;j++)22         {23             if(temp+a[j]<a[j])24             {25 //                left=right=j;//刚开始这里错了，不能直接转过去，先存到x中26                 temp=a[j];27                 x=j;28             }29             else30                 temp+=a[j];31             if(temp>maxd)32             {33                 maxd=temp;34                 left=x;35                 right=j;36             }37         }38         printf("Case %d:\n",i);39         printf("%d %d %d\n",maxd,left+1,right+1);40         if(i!=T);41         printf("\n");42     }43 }

后来的做法:

 1 //状态方程：dp[j]=max(dp[j-1]+a[j],a[j]); 2 //dp[0]=a[0]; 3 #include <iostream> 4 using namespace std; 5 int dp[100001]; 6 int a[100001]; 7 int re_start[100001]; 8 int main() 9 {10      int i,t;11   cin>>t;12   for(i=1;i<=t;i++)13   {14    int n,j;15    cin>>n;16    for(j=0;j<n;j++)17     cin>>a[j];18    dp[0]=a[0];19    re_start[0]=0;20    for(j=1;j<n;j++)21    {22            if(dp[j-1]+a[j]>=a[j])23      {24       dp[j]=dp[j-1]+a[j];25       re_start[j]=re_start[j-1];26      }27      else28      {29       dp[j]=a[j];30       re_start[j]=j;31      }32    }33    int d=dp[0];34    for(j=0;j<n;j++)35     if(dp[j]>d)36      d=dp[j];37     printf("Case %d:\n",i);38     for(j=0;j<n;j++)39      if(d==dp[j])40      {41       printf("%d %d %d\n",d,re_start[j]+1,j+1);42       break;43      }44      if(i!=t)45       printf("\n"); 46   }47   return 0;48 }
View Code

 

HDU_1003Max Sum 简单动归


联系
我们