动态规划免费馅饼

本文主要是介绍动态规划免费馅饼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}