2 qq 32650831 qq_32650831 于 2016.02.13 18:59 提问

c语言的一道题 动态规划 新手,求大神看看我代码的问题

描述
7
3 8
8 1 0
2 7 4 4
4 5 6 2 5
(图1)
图1显示了一个三角形数。 编写一个程序,计算最高金额的数字传递路线,从顶部开始和结束的地方固定在底座上。 每一步可以走斜向下向左或向右斜下。
输入
程序从标准输入读取。 第一行包含一个整数N:三角形的行数。 以下N行描述三角形的数据。 在三角形的行数> 1但< = 100。 三角形的数量,所有的整数,在0到99之间。
输出
你的程序是编写到标准输出。 最高金额写成一个整数。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30

我的代码是:

#include
int main()
{
int a[101][101]={0},n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);

for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        a[i][j]+=(a[i][j-1]>a[i-1][j-1]?a[i][j-1]:a[i-1][j-1]);
printf("%d\n",a[n][n]);
return 0;

}

6个回答

AgoniAngel
AgoniAngel   Rxr 2016.02.13 21:36
已采纳

ACM中的数塔问题。最大的数经过动态规划后应该在最顶层,也就是a[1][1]。

 a[i][j]+=(a[i][j-1]>a[i-1][j-1]?a[i][j-1]:a[i-1][j-1]);
 /*要改成*/
 a[i][j]+=(a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1]);

完整的代码应该是

#include <stdio.h>
#include <string.h>
int a[110][110];
int main()
{
    int i,j,n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));

        for(i=1; i<=n; i++)
            for(j=1; j<=i; j++)
                scanf("%d",&a[i][j]);

        for(i=n-1; i>=1; i--)
            for(j=1; j<=i; j++)
                 a[i][j]+=(a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1]);

        printf("%d\n",a[1][1]);
    }
    return 0;
}
caozhy
caozhy   Ds   Rxr 2016.02.13 21:43

图片说明

caozhy
caozhy   Ds   Rxr 2016.02.13 21:43

#include<stdio.h>

int max(int a, int b)
{
    if (a > b) return a; else return b;
}

int a[1001][1001],f[1001][1001];
int n;
int main()
{
  int i,j;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
      scanf("%d",&a[i][j]);
  for(i=1;i<=n;i++)
    f[n][i]=a[n][i];
  for(i=n-1;i>=1;i--)
    for(j=1;j<=i;j++)
      f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
  printf("%d\n",f[1][1]);
  return 0;
}      
leilba
leilba   Rxr 2016.02.13 19:56

是不是最后忘了取最大值?

 #include <stdio.h>
int main()
{
    int a[101][101]={0},n,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
            scanf("%d",&a[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
            a[i][j]+=(a[i][j-1]>a[i-1][j-1]?a[i][j-1]:a[i-1][j-1]);

    int maxn = -1;
    for(int i=1;i<=n;i++)
    {
        if (a[i][n]>maxn) {
            maxn = a[i][n];
        }
    }
    printf("%d\n",maxn);
    return 0;
}

qq_32650831
qq_32650831 试了下,还是wronganswer
接近 2 年之前 回复
qq_32650831
qq_32650831   2016.02.13 19:00

我的提交后显示wronganswer

qq_32650831
qq_32650831 南阳理工学院的oj
接近 2 年之前 回复
zhengjianfeng1103
zhengjianfeng1103 回复朝朝暮暮 : 那个代码评测软件
接近 2 年之前 回复
91program
91program   Ds   Rxr 2016.02.13 19:28

数组的下标是从 0 开始,不是 1。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!