当前位置:编程学习 > C/C++ >>

HDU 2845 Beans

思路:动态规划

  对于一行来说,相邻的数不可同时取,容易得到状态转移方程:

           dp[i]=max(dp[i-2]+a[i],dp[i-1]);  然后取每一行的最大得b[i] ,又可看作一行相同处理
       
           (注意左边i为1,2时的特殊情况)www.zzzyk.com

[cpp] 
<span style="font-size:18px; "><span style="color: rgb(255, 0, 0); ">#include<stdio.h> 
#define max(a,b) (a)>(b)?(a):(b) 
#define N 200010 
int dp[N],a[N],b[N]; 
int main() 

    int n,m,i,j; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
       dp[0]=a[0]=b[0]=0; 
       for(i=1;i<=n;i++) 
       { 
           for(j=1;j<=m;j++) 
              scanf("%d",&a[j]); 
           dp[1]=a[1]; 
           for(j=2;j<=m;j++) 
             dp[j]=max(dp[j-2]+a[j],dp[j-1]); 
           b[i]=dp[m]; 
       } 
       dp[1]=b[1]; 
       for(i=2;i<=n;i++) 
          dp[i]=max(dp[i-2]+b[i],dp[i-1]); 
       printf("%d\n",dp[n]); 
     
    } 
    return 0; 
}</span></span> 


 

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,