动态规划 免费馅饼

1.免费馅饼问题

                     5 (起始位置）

     4       |      5       |       6

3   4   5  |  4   5   6  |  5   6   7

..................

和“数塔”一样，它也是从某一点出发，有多个选择的问题（往前走一步，呆在原地，往后走一步）从中选择一条最优值路径（获得馅饼最多）。还是按照“数塔”的思考方式，我们可以假设“已经求得”下一个站在位置4获得的最大值x和呆在原地获得的最大值y以及站在位置6获得的最大值z,那么对于起始位置5获得最大值就是Max(x,y,z) ，因此可以得到状态转移方程为：m[t][x] = Max(m[t+1][x-1] , m[t+1][x] , m[t+1][x+1])

并且我们可以通过“列表格”的方式，自底向上求解：

#include    <stdio.h>
#include    <string.h>

#define     N    100000
int         a[N][11];

int    Max(int a , int b , int c)
{
    int        n;

    n = a > b ? a : b;

    return    n > c ? n : c;
}

int main(void)
{
    int        n , x , t , max , i;

    while(scanf("%d",&n))
    {
        if(!n)    break;

        max = 0;
        memset(a , 0 , sizeof(a));
        for(i = 0 ; i < n ; i++)
        {
            scanf("%d%d",&x,&t);
            a[t][x] += 1;
            if(t > max) max = t;
        }

        //DP
        for(t = max - 1 ; t >= 0 ; t--)
        {
            a[t][0] += Max(0 , a[t + 1][0] , a[t + 1][1]) ;

            for(x = 1 ; x < 10 ; x++)
            {
                a[t][x] += Max(a[t + 1][x - 1] , a[t + 1][x] , a[t + 1][x + 1]) ;
            }
            a[t][10] += Max(a[t + 1][9] , a[t + 1][10] , 0) ;
         }
        printf("%d\n",a[0][5]);
    }

    return    0;
}