柚子快报邀请码778899分享:简单DP
1.一只小蜜蜂
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 其中,蜂房的结构如下所示。
Input输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0 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 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\n",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 Output对于每个测试实例,请输出全部的满足要求的涂法,每个实例的输出占一行。 Sample Input 1 2 Sample Output 3 8解题思路:这道题师哥作为一道例题来给我们讲,他使用的是二维DP,使用一个二维数组,第一个参数代表动态规划进行到的阶段,第二个参数代表动态规划进行的状态,在这里我们划分了3个状态,分别是字符为E、O、F。E和F之前的字符可以是E、F、O,而O由于条件的限制不能重复出现,所以关于O的递推公式需要单独拿出来写,O之前只能出现E、F。 1 #include 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\n",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 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 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 2 #include 3 #include 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\n",dp[1][1]); 36 } 37 return 0; 38 } 4.分割折线平面 我们看到过很多直线分割平面的题目,今天的这个题目稍微有些变化,我们要求的是n条折线分割平面的最大数目。比如,一条折线可以将平面分成两部分,两条折线最多可以将平面分成7部分,具体如下所示。 Input输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(0 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 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\n",a[n]); 18 } 19 } 柚子快报邀请码778899分享:简单DP 相关文章
发表评论