AcWing 1015. 摘花生    原题链接    简单

作者： 作者的头像   Conan15 ,  2021-10-24 16:34:20 ,  所有人可见 ,  阅读 833

10


$$摘花生$$

首先，我们知道，对于每一个点，它只能从上面或左边转移而来。
那么，对于这一个点，我们当然会选取上面和左边中价值最大的进行转移。
所以，我们可以设定一个二维数组：int f[110][110]，存储从$a_{1,1}$到$a_{x,y}$的最大价值。
状态转移方程就是：$f_{x,y}=max(f_{x-1,y},f_{x,y-1})+a_{x,y}$
最后献上代码：（我的代码没有开$f$数组，是边读入边处理的，直接在$a$数组上进行修改）

#include <bits/stdc++.h>
using namespace std;
int T, a[110][110], n, m;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1;i <= n; i++)
            for (int j = 1;j <= m; j++) {
                scanf ("%d", &a[i][j]);
                a[i][j] += max(a[i - 1][j], a[i][j - 1]);
            }
        printf("%d\n", a[n][m]);
    }
    return 0;
}

运行时间$336ms$

10 评论

用户头像
RC_   2022-01-20 10:26         踩      回复

为什么最后输出a[ i ] [ j ]不对呢，到最后输出的i，j不就相当于n，m了吗

用户头像
Conan15   2022-01-20 11:39         踩      回复

因为i，j是循环中的变量，也就是局部变量。
出了循环就消失了，也就是在循环外不能使用。
你是代码CE吗？

用户头像
RC_   2022-01-20 12:41    回复了 Conan15 的评论         踩      回复

没有 就是调试的时候结果结果为0

用户头像
RC_   2022-01-20 12:41    回复了 Conan15 的评论         踩      回复

把i j定义到循环外也不对

用户头像
Conan15   2022-01-20 12:45    回复了 RC_ 的评论         踩      回复

代码在这里发一下，代码前后记得要加上```

用户头像
RC_   2022-01-20 12:51    回复了 Conan15 的评论         踩      回复 
#include<cstdio>
#include<iostream>

using namespace std;

const int N=1010;
int arr[N][N];

int main()
{
    int T;
    int r,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&r,&c);
        for(int i=1;i<=r;i++)
         for(int j=1;j<=c;j++)
         {
            scanf("%d",&arr[i][j]);
         }

       for(int i=1;i<=r;i++)
         for(int j=1;j<=c;j++)
         {
            arr[i][j]=max(arr[i-1][j]+arr[i][j],arr[i][j-1]+arr[i][j]);//动态规划模板（取两种情况的最大值）
         }
         printf("%d\n",arr[r][c]);
    }
    return 0;
}
用户头像
Conan15   2022-01-20 13:49    回复了 RC_ 的评论         踩      回复

这不是对的吗？AC了呀

用户头像
RC_   2022-01-20 15:40    回复了 Conan15 的评论         踩      回复 
#include<cstdio>
#include<iostream>

using namespace std;

const int N=1010;
int arr[N][N];

int main()
{
    int T;
    int i,j;
    int r,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&r,&c);
        for(int i=1;i<=r;i++)
         for(int j=1;j<=c;j++)
         {
            scanf("%d",&arr[i][j]);
         }

       for(i=1;i<=r;i++)
         for(j=1;j<=c;j++)
         {
            arr[i][j]=max(arr[i-1][j]+arr[i][j],arr[i][j-1]+arr[i][j]);//动态规划模板（取两种情况的最大值）
         }
         printf("%d\n",arr[i][j]);
    }
    return 0;
}

复制错了不好意思

用户头像
Conan15   2022-01-20 18:47    回复了 RC_ 的评论         踩      回复

我懂了，你的后面的双重循环，当i>r && j>c的时候停止，这个时候i == r + 1，j == c + 1
所以应该减一
改为这样

#include<cstdio>
#include<iostream>

using namespace std;

const int N=1010;
int arr[N][N];

int main()
{
    int T;
    int i,j;
    int r,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&r,&c);
        for(int i=1;i<=r;i++)
         for(int j=1;j<=c;j++)
         {
            scanf("%d",&arr[i][j]);
         }

       for(i=1;i<=r;i++)
         for(j=1;j<=c;j++)
         {
            arr[i][j]=max(arr[i-1][j]+arr[i][j],arr[i][j-1]+arr[i][j]);//动态规划模板（取两种情况的最大值）
         }
         printf("%d\n",arr[i - 1][j - 1]);
    }
    return 0;
}
用户头像
RC_   2022-01-20 21:21    回复了 Conan15 的评论         踩      回复

对哦 明白了 多谢