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++ ,