吃土豆
时间限制：1000 ms  |  内存限制：65535 KB
难度：4
描述
Bean-eating is an interesting game, everyone owns an M*N matrix, which is filled with different qualities beans. Meantime, there is only one bean in any 1*1 grid. Now you want to eat the beans and collect the qualities, but everyone must obey by the following rules: if you eat the bean at the coordinate(x, y), you can’t eat the beans anyway at the coordinates listed (if exiting): (x, y-1), (x, y+1), and the both rows whose abscissas are x-1 and x+1.



Now, how much qualities can you eat and then get ?
输入
There are a few cases. In each case, there are two integer M (row number) and N (column number). The next M lines each contain N integers, representing the qualities of the beans. We can make sure that the quality of bean isn't beyond 1000, and 1<=M,N<=500.
输出
For each case, you just output the MAX qualities you can eat and then get.
样例输入
4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6
样例输出
242

    #include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

int a[505][505];
int Max,m,n;
void DFS(int x,int y,int temp)
{
    if(x<0||x>m-1||y<0||y>n-1)
        return;
    if(Max<temp)
        Max=temp;
    DFS(x+1,y+1,temp+a[x+1][y+1]);//调试时是这一步出错，，求指教、
    DFS(x-1,y+1,temp+a[x-1][y+1]);
    DFS(x-1,y-1,temp+a[x-1][y-1]);
    DFS(x+1,y-1,temp+a[x+1][y-1]);
}

int main()
{
    while(cin>>m>>n)
    {
        freopen("1.txt","r",stdin);
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                cin>>a[i][j];
        Max=0;
        DFS(0,0,0);
        cout<<Max<<endl;
    }
    return 0;
}

递归没有合理的退出，最后栈溢出了。
经调试（VC6）：第一次进入递归时，栈指针为1244948，调试出现错误时，栈指针为208848，共使用了0.98M栈空间，加上其他的占用，显然栈溢出了。
你这个递归明显的错误就是会反复对吃过的豆子再吃，应该对吃过的豆子打标签。

好的 谢谢。

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

int a[505][505];
bool flag[505][505];
int Max,m,n;
void DFS(int x,int y,int temp)
{
    if(x<1||x>m||y<1||y>n)
        return;
    if(Max<temp)
        Max=temp;
    if(!flag[x][y])
    {
        flag[x][y]=true;
        DFS(x+1,y+1,temp+a[x][y]);
        flag[x][y]=false;
        
        flag[x][y]=true;
        DFS(x-1,y+1,temp+a[x][y]);
        flag[x][y]=false;
        
        flag[x][y]=true;
        DFS(x-1,y-1,temp+a[x][y]);
        flag[x][y]=false;
        
        flag[x][y]=true;
        DFS(x+1,y-1,temp+a[x][y]);
        flag[x][y]=false;
    }
}

int main()
{
    while(cin>>m>>n)
    {
        freopen("1.txt","r",stdin);
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        Max=0;
        memset(flag,false,sizeof(flag));
        DFS(0,0,0);
        cout<<Max<<endl;
    }
    return 0;
}

改过了，怎么还是不对？哪里出错了，，请各位路过的大佬指点下。

先谢谢各位了。

你这个递归根本没执行，你递归的条件是x<1||y<1 return，显然你给出坐标0，0是满足退出的条件的，所以执行不到递归处。
另外我觉得你对题意理解有错误，题意是说从你所处坐标，你不能吃y+1、y-1的豆子，也不能吃x+1、x-1处豆子，是指你即不能吃你左右相邻的豆子，也不能吃上下两行的豆子，不是不能吃“上下左右相邻”的豆子，而你算法是避开“上下左右相邻”的豆子和。
最后不能只从坐标0，0处开吃，遍历的话至少要遍历到m/2、n/2处的坐标才能得到最大和。

收到的鲜花

• 九转星河 于 2018-04-10 16:09 送鲜花  1朵   附言：讲解到位~
• 花脸 于 2018-04-10 22:42 送鲜花  1朵   附言：到位

https://bbs.bccn.net/viewthread.php?tid=476468&highlight=%B4%F3%D1%A7



看了6楼的解释后,记得和这个帖子里面的C题目几乎一样(附加一句把英文题目附加一下中文翻译或者别人解题积极性会高一点)~

可以这样,求选每一行最大能选多少,可以知道每一行中间相隔一个或者相隔两个才有可能取得最大值~
其中每相邻两个数取值共有3种情况~

其中0代表不选,1代表选~

00
01
10

这样可以以这三组数据同时dp找其中最大值,末尾为00的最大值,末尾为01的最大值,末尾为10的最大值(因为元素个数为偶数的所有组合都可以通过这三种不同的路径拼接而来的,然后会发现在没有负权的情况下,下一次00的权值是等于这次的01,下一次01的权值是等于这次的10和01这两个权值的较大值,下一次10权值是等于这次的00和10这两个权值的较大值)~

求出每一行的最大值后用同样的方法把这些最大值进行dp就可以了,时间复杂度应该是o(N*M)~

[此贴子已经被作者于2018-4-10 17:12编辑过]

其实这题可以引申为每行元素相隔为K而不是1,下面这个是求相隔为1也就是和题意吻合的情况~

下面只是求了其中一行的最大值~

#include<stdio.h>
#include<assert.h>

unsigned fun( const unsigned [],size_t );

int main( void )
{
    #define __ARR_LEN( s )    \
        (sizeof (s)/sizeof (*s))
                                        
    const unsigned a[]={3,6,2,1,10};
    
    printf("%u\n",fun(a,__ARR_LEN(a)));
    
    return 0;
    
    #undef __ARR_SIZE
}

unsigned fun( const unsigned a[],size_t _len )
{
    #define __MAX( a,b )    \
        ((a)>(b)?(a):(b))
    
    unsigned s[4]={0,0,0,0};
    
    const size_t len=_len-(_len&1);
    
    size_t i;
    
    assert(a);
    
    for (i=0;i!=len;i+=2)
    {
        s[0]=s[1];
        s[1]=s[2];
        s[2]=__MAX(s[2],s[3])+a[i+1];
        s[3]=__MAX(s[0],s[3])+a[i];
    }

    if (_len&1)
    {
        s[1]+=a[i];
        s[3]+=a[i];
    }
    
    return __MAX(s[1],__MAX(s[2],s[3]));
    
    #undef __MAX
}

[此贴子已经被作者于2018-4-10 19:34编辑过]

收到的鲜花

• 花脸 于 2018-04-10 22:56 送鲜花  1朵   附言：谢谢 又学到了不少知识。

好的 谢谢