总结一下做递推题的经验，一般都开成long long （别看项数少，随便就超了） 一般从第 i 项开始推其与前面项的关系（动态规划也是这样），而不是从第i
项推其与后面的项的关系。
hdu2044:http://acm.hdu.edu.cn/showproblem.php?pid=2044
//没开成long long WA了一次 #include<iostream> #include<cstdio> #include<algorithm> #include <string.h> #include <math.h> using namespace std; long long f[52][52];///表示a - b的方案数 int main() { for(int i=0;i<50;i++){ f[i][i]=0; f[i][i+1]=1; f[i][i+2]=2; } for(int i=1;i<50;i++){ for(int j=i+3;j<50;j++){ f[i][j]=f[i][j-1]+f[i][j-2]; } } int tcase; scanf("%d",&tcase); while(tcase--){ int a,b; scanf("%d%d",&a,&b); printf("%lld ",f[a][b]); } return 0; }
hdu2045:http://acm.hdu.edu.cn/showproblem.php?pid=2045
#include<iostream> #include<cstdio> #include<algorithm> #include <string.h> #include <math.h> using namespace std; ///第 n 种方案由前 n-1种方案决定 ///如果 第 n-1 个格子和 第 1个格子涂色方案不同，那么第n个格子可选方案只有一种, f[n] = f[n-1]; ///若第n-1个格子和第1个格子相同，此时为f(n-2)再乘第n-1个格子的颜色数，这样为2*f(n-2)； long long f[51]; int main() { f[1]=3; f[2]=6; f[3]=6; for(int i=4;i<=50;i++) f[i]=f[i-1]+2*f[i-2]; int n; while(scanf("%d",&n)!=EOF) { printf("%lld ",f[n]); } return 0; }
hdu 2046:http://acm.hdu.edu.cn/showproblem.php?pid=2046
#include<iostream> #include<cstdio> #include<algorithm> #include <string.h> #include <math.h> using namespace std; ///前 i 个格子如果在第i列放竖着放一根1*2的格子，那么 f[i] = f[i-1] ///如果在第 i-1列和第 i列横着放两根1*2的格子，那么f[i] = f[i-2] ///f[i] = f[i-1]+f[i-2] long long f[51]; int main() { f[1]=1; f[2]=2; for(int i=3;i<=50;i++) f[i]=f[i-1]+f[i-2]; int n; while(scanf("%d",&n)!=EOF){ printf("%lld ",f[n]); } return 0; }
hdu 2047:http://acm.hdu.edu.cn/showproblem.php?pid=2047
#include<iostream> #include<cstdio> #include<algorithm> #include <string.h> #include <math.h> using namespace std; ///如果第 n个字符为 'E'或者'F',那么前n-1个没有任何限定 f[n] = 2*f[n-1] ///如果为'O' ,那么第 n-1个格子只能选'E'或'F',前n-2没有限定,f[n] = 2*f[n-2] ///f[n]=2*f[n-1]+2*f[n-2] long long f[41]; int main() { f[1] = 3; f[2] = 8; for(int i=3;i<40;i++) f[i]=2*f[i-1]+2*f[i-2]; int n; while(scanf("%d",&n)!=EOF) { printf("%I64d ",f[n]); } return 0; }
hdu 2048:http://acm.hdu.edu.cn/showproblem.php?pid=2048
这题开始不会做。。然后知道了错排公式：错排公式
果然弄数学功底很重要啊。。然后就很容易了。
#include<iostream> #include<cstdio> #include<algorithm> #include <string.h> #include <math.h> using namespace std; ///错排：考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上， ///那么这样的排列就称为原排列的一个错排。 ///当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么 /// D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推. ///第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法； ///第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于 ///第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于 ///这n-1个元素，有D(n-1)种方法； ///所以得到错排公式：f[i] = (i-1)*(f[i-1]+f[i-2]) ///解题思路：错排除以全排列 (有意思的是，到8以后这个几率就恒定了) long long f[21]; int main() { f[1] = 1; f[2] = 1; f[3] = 2; for(int i=4;i<=20;i++) f[i]=(i-1)*f[i-1]+(i-1)*f[i-2]; int tcase; scanf("%d",&tcase); while(tcase--) { int n; scanf("%d",&n); long long k =1; for(int i=1;i<=n;i++) k*=i; printf("%.2lf%% ",f[n]*1.0/k*100); } return 0; }
hdu 2049:http://acm.hdu.edu.cn/showproblem.php?pid=2049
知道错排公式就会了。
#include<iostream> #include<cstdio> #include<algorithm> #include <string.h> #include <math.h> using namespace std; ///M个数有f[M]种错排，N里面选M个数有C(M,N)=n!/(m!*(n-m)!) = n!/m!/(n-m)!种可能, ///所以 f[M]*C(M,N)即为所求 long long f[21]; int main() { f[1] = 1; f[2] = 1; f[3] = 2; for(int i=4;i<=20;i++) f[i]=(i-1)*f[i-1]+(i-1)*f[i-2]; int tcase; scanf("%d",&tcase); while(tcase--) { int n,m; scanf("%d%d",&n,&m); long long k =1; int t = n-m; for(int i=n;i>m;i--){ k*=i; while(k%t==0&&t!=1){ k=k/t; t--; } } printf("%lld ",f[m]*k); } return 0; }
hdu 2050:http://acm.hdu.edu.cn/showproblem.php?pid=2050
我按照自己的想法做，然后AC了。。但没法证明。。。具体证明看这里：http://www.cnblogs.com/chaosheng/archive/2012/01/26/2329583.html
#include<iostream> #include<cstdio> #include<algorithm> #include <string.h> #include <math.h> using namespace std; ///这个题没两条折线之间要分割的平面尽可能的多，那么每两条之间都会有四个交点 ///所以当n条折线时，会多出4*n*(n-1)/2个点。。然后我加上原来的n个顶点，就得到所有顶点的个数 ///然后+1就是答案。。 int main() { int tcase; scanf("%d",&tcase); while(tcase--) { int n; scanf("%d",&n ); printf("%d ",2*n*n-n+1); } return 0; }