简单DP

1.一只小蜜蜂

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

Input输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。
Output对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。
Sample Input

2
1 2
3 6

Sample Output

1
3


解题思路：从1-2有1种方法，从1-3可以由1-3或1-2-3，总共2种，由1-4可由1-2-3-4或1-3-4或1-2-4总共3种，可以这样想：想到达4必需到达3或2，然后计算到达3或2的所有路线，加起来就是所有的
路线数，得到递推公式 f(4)=f(3)+f(2)；由此可以想到斐波那契数列，不过此题还要注意数据量的大小，每次打表都要注意。

 1 #include<stdio.h>
 2 #define LL long long int
 3 LL dp[55];
 4 int main()
 5 {
 6     LL t,i,a,b,ans;
 7     dp[2]=1;
 8     dp[3]=2;
 9     for(i=4;i<=54;i++)
10     {
11         dp[i]=dp[i-1]+dp[i-2];
12     }
13     scanf("%lld",&t);
14     while(t--)
15     {
16         scanf("%lld%lld",&a,&b);
17         ans=dp[b-a+1];
18         printf("%lld
",ans);
19     }
20     return 0;
21 }

2.阿牛和EOF牛肉干

今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做EOF的队伍，由04级的阿牛、XC以及05级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了一想，阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由"E" "O" "F"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,阿牛同时禁止在串中出现O相邻的情况，他认为，"OO"看起来就像发怒的眼睛，效果不好。

你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？

PS: 阿牛还有一个小秘密，就是准备把这个刻有 EOF的牛肉干，作为神秘礼物献给杭电五十周年校庆，可以想象，当校长接过这块牛肉干的时候该有多高兴！这里，请允许我代表杭电的ACMer向阿牛表示感谢！

再次感谢！

Input输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0<n<40)。
Output对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。
Sample Input

1
2

Sample Output

3
8


解题思路：这道题师哥作为一道例题来给我们讲，他使用的是二维DP，使用一个二维数组，第一个参数代表动态规划进行到的阶段，第二个参数代表动态规划进行的状态，在这里我们划分了3个状态，分别
是字符为Ｅ、Ｏ、Ｆ。Ｅ和Ｆ之前的字符可以是E、F、O，而O由于条件的限制不能重复出现，所以关于O的递推公式需要单独拿出来写，O之前只能出现E、F。

 1 #include<stdio.h>
 2 #define LL long long int
 3 LL dp[60][3];
 4 LL ans[60];
 5 int main()
 6 {
 7     LL n,i;
 8     dp[1][0]=1;///0
 9     dp[1][1]=1;///E
10     dp[1][2]=1;///F
11     ans[1]=3;
12     for(i=2;i<59;i++)
13     {
14         dp[i][0]=dp[i-1][1]+dp[i-1][2];///O不能出现重复,之前的字母只能是E或者F
15         dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
16         dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
17         ans[i]=dp[i][0]+dp[i][1]+dp[i][2];
18     }
19     while(scanf("%lld",&n)!=EOF)
20     {
21         printf("%lld
",ans[n]);
22     }
23     return 0;
24 }

一维DP：最后一个字符只可能有三种情况：E，F，O；最后总的涂法为F（n）;当是E的时候倒数第二个字符可以随便涂，因而为此涂法数为：F（n-1）;当是F的时候倒数第二个字符也可以随便涂，因而为此涂法数也为：F（n-1）;当是O的时候，倒数第二个字符不能随便了，因为连续的2个O是不符合要求的，因此O的时候又被分为二种情况为E或F。在最后2个字符为EO的情况下，倒数第三个字符可以随便，因此此涂法为F（n-2）;在最后2个字符为FO的情况下，倒数第三个字符也可以随便，因此此涂法也为F（n-2）;此时已经讲所有的情况考虑完毕，F（n）=2*F(n-1)+2*F(n-2);

1 dp[1]=3;
2 dp[2]=8;
3 for(i=2; i<59; i++)
4 {
5     dp[i]=2*dp[i-1]+2*dp[i-2];
6 }

3.数塔

Problem Description

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?

Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

Output

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

Sample Input

Sample Output

30

解题思路：从下（倒数第二行起）往上（第一行），使得每个位置的数都等于它本身加上（它正下方的数字与斜右方的数字中比较大的那个数），直到最后，第一行的数字就变成可能得到的最大和。dp方程：dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])；dp[i][j]=dp[i][j]+a[i][j]。

 1 #include<string.h>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int main()
 6 {
 7     int t,n,i,j;
 8     int a[110][110];
 9     int dp[110][110];
10     scanf("%d",&t);
11     while(t--)
12     {
13         memset(dp,0,sizeof(dp));
14         memset(a,0,sizeof(a));
15         scanf("%d",&n);
16         for(i=1; i<=n; i++)
17         {
18             for(j=1; j<=i; j++)
19             {
20                 scanf("%d",&a[i][j]);
21             }
22         }
23         for(i=1; i<=n; i++)
24             {
25                 dp[n][i]=a[n][i];
26             }
27         for(i=n-1; i>=0; i--)
28         {
29             for(j=1; j<=i; j++)
30             {
31                 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1]);
32                 dp[i][j]=dp[i][j]+a[i][j];
33             }
34         }
35         printf("%d
",dp[1][1]);
36     }
37     return 0;
38 }

4.分割折线平面

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。

Input输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0<n<=10000),表示折线的数量。

Output对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。

Sample Input

2
1
2

Sample Output

2
7

解题思路：

对n取任意值时，分割平面数= 交点数 + 顶点数 + 1，我们假设f（n-1）已知，又f（n）每一条拆线与另一条拆线交点为4，则新加第N条拆线交点数增加4*(n-1)
顶点数比f（n-1）多一个，故f（n）=f（n-1）+4*（n-1）+1

 1 #include<cstdio>
 2 #define LL long long int
 3 LL a[10010];
 4 int main()
 5 {
 6     LL n,i,t;
 7     a[1]=2;
 8     a[2]=7;
 9     for(i=3;i<=10009;i++)
10     {
11         a[i]=a[i-1]+4*(i-1)+1;
12     }
13     scanf("%lld",&t);
14     while(t--)
15     {
16         scanf("%lld",&n);
17         printf("%lld
",a[n]);
18     }
19 }