题目内容

P1508

大意:正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处在饥饿的状态中。某日上课,正当他饿得头昏眼花之时,眼前突然闪现出了一个n*m(n and m<=200)的矩型的巨型大餐桌,而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了n*m个小方格,每一个方格中都有一个圆形的巨型大餐盘,上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分(有些是负的,因为吃了要拉肚子),他决定从自己所处的位置吃到餐桌的另一侧,但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。

由于李大水牛已饿得不想动脑了,而他又想获得最大的能量,因此,他将这个问题交给了你。

每组数据的出发点都是最后一行的中间位置的下方!

解题思路

第一反应:这东西可以用 bfs!!!

结果由于不擅长卡常或者算法错误 TLE 了,开始想并不难的 dp 正解,大体思路和数字三角形类似。

第一次 AC 的想法比较复杂,完全按照题目思路模拟的,当然也 A 了,是每一次都进行严格的边界判断,确保不会从不该来的地方过来。具体思路就不说了,太繁杂。

#include <cstdio>

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=205;
int n,m,f[maxn][maxn],v[maxn][maxn];

int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&v[i][j]);
    int mid=n/2+1;
    for(int l=m;l>=1;l--)
        for(int c=-(m-l+1);c<=(m-l+1);c++)
        {
            int cc=mid+c;
            if(cc<1)
                continue;
            if(cc>n)
                break;
            if(c>l-m)
                f[l][cc]=max(f[l][cc],f[l+1][cc-1]+v[l][cc]);
            if(c<m-l)
                f[l][cc]=max(f[l][cc],f[l+1][cc+1]+v[l][cc]);
            if(c<=m-l&&c>=l-m)
                f[l][cc]=max(f[l][cc],f[l+1][cc]+v[l][cc]);
        }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[1][i]);
    printf("%d\n",ans);
    return 0;
}

结果看了一圈题解发现,完全不需要进行如此严格的判定,而且可以在线推,为什么呢?因为他完全就是数字三角形的变种,直接推下去,最后取最大值的时候只取李大水牛前方,左右前方的三个点就可以了,这样保证得到的结果是正确的,是李大水牛可以吃到的路线。直接边读入边处理即可。

#include <cstdio>

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=205;
int n,m,f[maxn][maxn];

int main()
{
    scanf("%d %d",&m,&n);
    int mid=n/2+1;
    for(int l=1;l<=m;l++)
        for(int c=1;c<=n;c++)
        {
            scanf("%d",&f[l][c]);
            f[l][c]=max(max(f[l-1][c],f[l-1][c+1]),f[l-1][c-1])+f[l][c];
        }
    printf("%d\n",max(f[m][mid],max(f[m][mid+1],f[m][mid-1])));
    return 0;
}
最后修改日期:2020年3月1日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。