hdu 2571 命运（递推，请小心）

题目　　　　

//不能广搜，会超内存
//可以用dp思想模拟
//map 后来保存的是 保存由前面推来的最大的幸运总值的点
//下标从1开始，不然倍数会有问题

//AC 代码：

AC代码

//不能广搜，会超内存
//可以用dp思想模拟
//map 后来保存的是 保存由前面推来的最大的幸运总值的点
//下标从1开始，不然倍数会有问题
//又错了那么多次。。。
//重写。。。
//求过！！！

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int t,n,m,i,j,k,map[25][1010];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);

        memset(map,-21000000,sizeof(map));
    
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                int maxx=-21000000;
                for(k=2;k<=m;k++)
                {
                    if(j%k==0)
                    {
                        maxx=maxx>map[i][j/k]? maxx:map[i][j/k];
                    }
                }
                if(maxx<map[i-1][j])maxx=map[i-1][j];
                if(maxx<map[i][j-1])maxx=map[i][j-1];
                if(!(i==1&&j==1))
                    map[i][j]+=maxx;
            }
        }

        printf("%d
",map[n][m]);
    }

    return 0;
}

//模拟时最好不要分开，因为我分开写错了——求高人指点为什么我分开写错掉了，明明思路是一样的啊

//错掉的代码：

//不能广搜，会超内存
//可以用dp思想模拟
//temp 保存由前面推来的最大的幸运总值的点

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
    int t,n,m,i,j,k,map[25][1010];
    int temp[25][1010];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        //一切要从1开始！！否则倍数有问题！！
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }

        //没有初始化?
        memset(temp,-21000000,sizeof(temp));
        
        temp[1][1]=map[1][1];
        //(x,y+1)
        for(j=2;j<=m;j++)
            temp[1][j]=map[1][j]+temp[1][j-1];
        //(x+1,y)
        for(i=2;i<=n;i++)
            temp[i][1]=map[i][1]+temp[i-1][1];
        //(x,y*k) 
        for(j=2;j<=m;j++)
        {
             for(k=2;k<=m;k++)
            {
                if(j%k==0)
                {
                    temp[1][j]=temp[1][j]>(map[1][j]+temp[1][j/k])? temp[1][j]:(map[1][j]+temp[1][j/k]);
                }
            }
        }
            
        for(i=2;i<=n;i++)
        {
            for(j=2;j<=m;j++)
            {
                //(x,y+1) 
                temp[i][j]=temp[i][j]>(map[i][j]+temp[i][j-1])? temp[i][j]:(map[i][j]+temp[i][j-1]);
                 //(x,y*k)
                for(k=2;k<=m;k++)
                {
                    if(j%k==0)
                    {
                        temp[i][j]=temp[i][j]>(map[i][j]+temp[i][j/k])? temp[i][j]:(map[i][j]+temp[i][j/k]);
                    }
                }
                //(x+1,y)
                temp[i][j]=temp[i][j]>(map[i][j]+temp[i-1][j])? temp[i][j]:(map[i][j]+temp[i-1][j]);
            }
        }
        printf("%d
",temp[n][m]);
    }

    return 0;
}