P1143 三取方格数

Published on 2009 / 10 / 20

初赛虽然是挂了，还是得做题~

这是一个比较经典的题的改编，当时是只取两条路，有点类似于某年NOIP的传纸条游戏。在Vijos里改成了三条路，这就增加了一点难度，我原来是直接开四维数组DP，这里就开六维数组肯定爆。开始优化。

具体方法是只记录横坐标和步数，纵坐标用横坐标于步数来求。

数据在20内，很容易秒杀。O(∩_∩)O~

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
Accepted 有效得分：100 有效耗时：0ms

#include<stdio.h>

int N,Num[20][20],Re[21][21][21][41];

void Search(int xa,int xb,int xc,int step)
{
    if(Re[xa][xb][xc][step]==0)
    {
        int ya,yb,yc;
        ya=step-xa-1;
        yb=step-xb-1;
        yc=step-xc-1;
        if(xa<N&&xb<N&&xc<N&&ya<N&&yb<N&&yc<N)
        {
            Re[xa][xb][xc][step]+=Num[xa][ya];
            if(xb!=xa) Re[xa][xb][xc][step]+=Num[xb][yb];
            if(xc!=xa&&xc!=xb) Re[xa][xb][xc][step]+=Num[xc][yc];
            int temp=0;
            Search(xa+1,xb+1,xc+1,step+1);
            if(temp<Re[xa+1][xb+1][xc+1][step+1])
                temp=Re[xa+1][xb+1][xc+1][step+1];
            Search(xa+1,xb+1,xc,step+1);
            if(temp<Re[xa+1][xb+1][xc][step+1])
                temp=Re[xa+1][xb+1][xc][step+1];
            Search(xa+1,xb,xc+1,step+1);
            if(temp<Re[xa+1][xb][xc+1][step+1])
                temp=Re[xa+1][xb][xc+1][step+1];  
            Search(xa,xb+1,xc+1,step+1);
            if(temp<Re[xa][xb+1][xc+1][step+1])
                temp=Re[xa][xb+1][xc+1][step+1];
            Search(xa,xb,xc+1,step+1);
            if(temp<Re[xa][xb][xc+1][step+1])
                temp=Re[xa][xb][xc+1][step+1];
            Search(xa,xb+1,xc,step+1);
            if(temp<Re[xa][xb+1][xc][step+1])
                temp=Re[xa][xb+1][xc][step+1];
            Search(xa+1,xb,xc,step+1);
            if(temp<Re[xa+1][xb][xc][step+1])
                temp=Re[xa+1][xb][xc][step+1];  
            Search(xa,xb,xc,step+1);
            if(temp<Re[xa][xb][xc][step+1])
                temp=Re[xa][xb][xc][step+1];
            Re[xa][xb][xc][step]+=temp;
        }
    }
}

int main()
{
    int a,b;
    scanf("%d",&N);
    for(a=0;a<N;a++)
        for(b=0;b<N;b++)
            scanf("%d",&Num[a][b]);
    Search(0,0,0,1);
    printf("%d\n",Re[0][0][0][1]);
    return 0;
}