P1133 教主的花园

题目地址

这是一道DP的题目 就是情况比较多
一共有四种情况
第一点为10 且上升 start=0 angle=1
第一点为20 且上升start=1 angle=1
第一点为20 且下降start=1 angle=-1
第一点为30 且下降start=2 angle=-1
分这四种情况DP四次 取最优结果就行了

初始化dp为-1
第一行dp[0][start]=input[0][start];

dp[i][j]=max(上个可选点集合)+input[i][j];
上个可选点的位置由当前位置j 和当前的方向angle决定
如果上个点不可到达 就dp[i][j]=-1;
每做完一行的dp对angle取个反表示方向变了

最后计算结果的时候要考虑start angle排除掉不可能的点
然后取最大值

做完4次DP取4次DP最大值就是结果

#include <stdio.h>

const int Type=3;

void init(int** dp,int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<Type;j++)
        {
            dp[i][j]=-1;
        }
    }
}

/**
 *angle 第一个数 1递增 -1递减
 */
int dpFunc(int** input,int** dp,int n,int start,int angle){
    init(dp,n);

    int i,j,k;
    dp[0][start]=input[0][start];

    int tmpAngle=angle;
    int max;

    for(i=1;i<n;i++)
    {
        for(j=0;j<Type;j++)
        {
            k=j-tmpAngle;
            max=-1;
            while (k>=0&&k<Type)
            {
                if(dp[i-1][k]>max)
                {
                    max=dp[i-1][k];
                }
                k-=tmpAngle;
            }

            if(max>0)
            {
                dp[i][j]=max+input[i][j];
            }
            
        }
        //这个点上升下一个点就下降
        tmpAngle=-tmpAngle;
    }

    k=start+angle;
    max=-1;
    while (k>=0&&k<Type)
    {
        if(dp[n-1][k]>max)
        {
            max=dp[n-1][k];
        }
        k+=angle;
    }

    
    return max;
}

int main(){
    int n;
    int i;
    scanf("%d",&n);
    int** input=new int*[n];
    int** dp=new int*[n];
    for(i=0;i<n;i++)
    {
        input[i]=new int[Type];
        dp[i]=new int[Type];
        scanf("%d %d %d",&input[i][0],&input[i][1],&input[i][2]);
    }

    int start=0,angle=1;
    int max=dpFunc(input,dp,n,start,angle);

    start=1;
    int tmp=dpFunc(input,dp,n,start,angle);
    if(tmp>max)
    {
        max=tmp;
    }

    angle=-1;
    tmp=dpFunc(input,dp,n,start,angle);
    if(tmp>max)
    {
        max=tmp;
    }

    start=2;
    tmp=dpFunc(input,dp,n,start,angle);
    if(tmp>max)
    {
        max=tmp;
    }

    printf("%d\n",max);


    for(i=0;i<n;i++)
    {
        delete input[i];
        delete dp[i];
    }
    delete input;
    delete dp;
    return 0;
}