hdu2084——数塔

以你之姓@ 2022-07-16 07:57 157阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=2084][http_acm.hdu.edu.cn_showproblem.php_pid_2084]

# 定位 #

*  简单动态规划
 *  水题

# 分析 #

*  自下而上求解问题，全局最优解一定包含局部最优解  
    
    
    *d**p*\[*i*\]\[*j*\]=*m**a**x*(*d**p*\[*i*\+1\]\[*j*\],*d**p*\[*i*\+1\]\[*j*\+1\])\+*a*\[*i*\]\[*j*\]
 *  空间优化：只需要开辟一个数组，在原数组上进行状态更新  
    
    
    *a*\[*i*\]\[*j*\]\+=*m**a**x*(*a*\[*i*\+1\]\[*j*\],*a*\[*i*\+1\]\[*j*\+1\])

# 代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int size = 0;
        int n = 0;
        int i = 0;
        int j = 0;
        int a[100][100];
    
        scanf("%d%*c",&size);
        while(size--)
        {
            memset(a,0,10000*sizeof(int));
            scanf("%d%*c",&n);
            for(i=0;i<n;i++)
            {
                for(j=0;j<=i;j++)
                {
                    scanf("%d%*c",&a[i][j]);
                }
            }
            for(i=n-2;i>=0;i--)
            {
                for(j=0;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[0][0]);
        }
        return 0;
    }

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">31MS</td> 
   <td align="center">1728K</td> 
   <td align="center">664 B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

*  具有多个测试实例的题目，注意存储空间的数据清理
 *  使用scanf()时，注意数据间隔符(空格、换行等)的处理

# 后记 #

采用朴素的自顶向下搜索的方法，在本题中也可以通过，但用时较多。

#include <stdio.h>
    #include <stdlib.h>
    #define MAX(x,y) ((x)<(y)?(y):(x))
    
    int main()
    {
        int size = 0;
        int n = 0;
        int fr = 0;
        int temp = 0;
        int i = 0;
        int j = 0;
        int result[5050] = {-1};
    
        scanf("%d%*c",&size);
        while(size--)
        {
            scanf("%d%*c",&n);
            scanf("%d%*c",&result[0]);
            for(i=1;i<n;i++)
            {
                fr = (i+1)*i/2;
                for(j=0;j<=i;j++)
                {
                    scanf("%d%*c",&temp);
                    if(j == 0)
                    {
                        result[fr+j] = result[fr-i] + temp;
                    }
                    else if(j == i)
                    {
                        result[fr+j] = result[fr-1] + temp;
                    }
                    else
                    {
                        result[fr+j] = MAX(result[fr-i+j-1],result[fr-i+j]) + temp;
                    }
                }
            }
            for(i=1;i<n;i++)
            {
                if(result[fr+i] > result[fr])
                {
                    result[fr] = result[fr+i];
                }
            }
            printf("%d\n",result[fr]);
        }
        return 0;
    }

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">78MS</td> 
   <td align="center">1700K</td> 
   <td align="center">1139 B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

[http_acm.hdu.edu.cn_showproblem.php_pid_2084]: http://acm.hdu.edu.cn/showproblem.php?pid=2084