hdu1176——免费馅饼

爱被打了一巴掌 2022-07-16 08:44 187阅读 0赞

# 地址 #

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

# 定位 #

*  简单动态规划
 *  升级版数塔
 *  水题

# 分析 #

*  将馅饼落地时间t在空间上展开，该问题便转化为数塔问题  
    最大下落时刻tmax => 数塔高度  
    t时刻x位置落下的馅饼数量 => a\[t\]\[x\]节点的值  
    dp\[0\]\[5\] => 数塔的根节点
 *  区别于数塔，本题宽度受限，即0<=x<=10  
    在t>9s后，三角形数塔退化为矩形。  
    宽度受限，使问题规模得以缩小，即使在0< T <10000的范围下，也不会超时。  
    宽度受限，使边界位置的递推式有不同。
 *  递推关系式  
    
    
    *d**p*\[*i*\]\[0\]=*m**a**x*(*d**p*\[*i*\+1\]\[0\],*d**p*\[*i*\+1\]\[1\])\+*a*\[*i*\]\[*j*\]
    
      
    
    
    *d**p*\[*i*\]\[*j*\]=*m**a**x*(*d**p*\[*i*\+1\]\[*j*−1\],*d**p*\[*i*\+1\]\[*j*\],*d**p*\[*i*\+1\]\[*j*\+1\])\+*a*\[*i*\]\[*j*\]
    
      
    
    
    *d**p*\[*i*\]\[10\]=*m**a**x*(*d**p*\[*i*\+1\]\[9\],*d**p*\[*i*\+1\]\[10\])\+*a*\[*i*\]\[*j*\]
 *  存储优化：只需要开辟一个数组，在原始数组上更新即可

# 代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    int MAX(int n1,int n2,int n3)
    {
        if(n1>n2)
        {
            if(n1>n3){
       return n1;}
            else{
       return n3;}
        }
        else
        {
            if(n2>n3){
       return n2;}
            else{
       return n3;}
        }
    }
    
    int main()
    {
        int n;
        int x,t;
        int i,j;
        int tmax = 0;
        int a[100001][11] = {
       0};
        scanf("%d*c",&n);
        while(n)
        {
            memset(a,0,sizeof(a));
            tmax = 0;
            while(n--)
            {
                scanf("%d %d*c",&x,&t);
                a[t][x]++;
                if(t > tmax)
                {
                    tmax = t;
                }
            }
            for(i=tmax-1;i>=0;i--)
            {
                a[i][0] += a[i+1][0]>a[i+1][1]?a[i+1][0]:a[i+1][1];
                for(j=1;j<10;j++)
                {
                    a[i][j] += MAX(a[i+1][j-1],a[i+1][j],a[i+1][j+1]);
                }
                a[i][10] += a[i+1][9]>a[i+1][10]?a[i+1][9]:a[i+1][10];
            }
            printf("%d\n",a[0][5]);
            scanf("%d*c",&n);
        }
        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">62MS</td> 
   <td align="center">5980K</td> 
   <td align="center">1035 B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

*  具有多个测试实例的题目，注意存储空间的数据清理

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