首页 > 代码库 > hdu2569(递推dp)

hdu2569(递推dp)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2569

 

分析:

f(n),n个珠子的合格数;
a(n),n个珠子,最后2个相同的合格数;
b(n),n个珠子,最后2个不同的合格数;
f(n)=a(n)+b(n);
a(n)=f(n-1);
b(n)=a(n-1)*2+b(n-1);
1.f(n)=a(n)+b(n)
2.f(n-1)=a(n-1)+b(n-1)
1 - 2得出结果
f(n)=2*f(n-1)+f(n-2);

 

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long longusing namespace std;LL f[50];void init(){    f[1]=3;f[2]=9;    for(int i=3;i<=40;i++)f[i]=2*f[i-1]+f[i-2];}int main(){    int t,n;    scanf("%d",&t);    init();    while(t--)    {        scanf("%d",&n);        printf("%I64d\n",f[n]);    }}
View Code

 

hdu2569(递推dp)