题目地址

显而易见 这是一道DP的题目
二维数组a[i][j]代表i棵树j高度有多少个柿子
dp[i][j]代表i棵树j高度最多能吃到多少柿子
i棵树j高度 可以由别的树k从j-Delta位置跳过来
也可以从i棵树j-1位置过来
所以状态转移方程为
dp[i][j]=a[i][j]+max(dp[i][j-1],dp[k][j-Delta])

看看输入数据 n h<2000
如果直接写dp 时间复杂为O(n^3)
最差情况 大概要计算80亿次 时间只有2秒 超时概率很大
我提交了下代码 很不幸超时了

#include <stdio.h>

int main(){
    int n,h,delta;
    scanf("%d %d %d",&n,&h,&delta);
    int i,j,k;
    int** input=new int*[n];
    int** dp=new int*[n];
    for( i=0;i<n;i++)
    {
        input[i]=new int[h];
        dp[i]=new int[h];
        for(j=0;j<h;j++)
        {
            input[i][j]=0;
            dp[i][j]=0;
        }
    }

    int ni,num;
    for( i=0;i<n;i++)
    {
        scanf("%d",&ni);
        for(j=0;j<ni;j++)
        {
            scanf("%d",&num);
            input[i][num-1]++;
        }
    }


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

    for(j=1;j<h;j++){
        for(i=0;i<n;i++)
        {
            int max=dp[i][j-1];
            if(j>=delta)
            {
                for(k=0;k<n;k++)
                {
                    if(k!=i)
                    {
                        if(max<dp[k][j-delta])
                        {
                            max=dp[k][j-delta];
                        }
                    }
                }
            }
            dp[i][j]=max+input[i][j];      
        }
    }

    int max=0;
    for( i=0;i<n;i++)
    {
        if(max<dp[i][h-1])
        {
            max=dp[i][h-1];
        }
    }
    printf("%d\n",max);

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

需要对该方法进行优化
状态转移方程
dp[i][j]=a[i][j]+max(dp[i][j-1],dp[k][j-Delta])
很明显我们只要知道j-Delta 高度所有树的最大值就可以了
不需要把每个树都遍历一遍
所以建立一个一维数组 dph[j]=max(dp[i][j])
状态转移方程变成
dp[i][j]=a[i][j]+max(dp[i][j-1],dph[j-Delta])
这样时间复杂度变成了O(n^2)

#include <stdio.h>

int main(){
    int n,h,delta;
    scanf("%d %d %d",&n,&h,&delta);
    int i,j,k;
    int** input=new int*[n];
    int** dp=new int*[n];
    int* dph=new int[h];
    for( i=0;i<n;i++)
    {
        input[i]=new int[h];
        dp[i]=new int[h];
        for(j=0;j<h;j++)
        {
            input[i][j]=0;
            dp[i][j]=0;
            dph[j]=0;
        }
    }

    int ni,num;
    for( i=0;i<n;i++)
    {
        scanf("%d",&ni);
        for(j=0;j<ni;j++)
        {
            scanf("%d",&num);
            input[i][num-1]++;
        }
    }


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

    for(j=1;j<h;j++){
        int maxh=0;
        for(i=0;i<n;i++)
        {
            int max=dp[i][j-1];
            if(j>=delta)
            {
                if(max<dph[j-delta])
                {
                    max=dph[j-delta];
                }
            }
            dp[i][j]=max+input[i][j];
            if(maxh<dp[i][j])
            {
                maxh=dp[i][j];
            }      
        }
        dph[j]=maxh;
    }
    printf("%d\n",dph[h-1]);

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