hdu 1165 递推

这种dp。。

刚开始做是用备忘录，结果栈溢出，后来不要递归，直接dp，发现数组远远不够大，肯定MLE，因为当m等于3，n等于23的时候已经好大好大了。。无耐之下百度，结果就发现是用递推公式做的，完全抄的。。

m=0时 A(m,n)=n+1;

m=1时 A(m,n)=A(0,A(1,n-1))=A(1,n-1)+1=A(1,n-2)+1+1=……=n+2;

m=2时 A(m,n)=n*2+3

m=3时 A(m,n)=A(2,A(m,n-1))=A(m,n-1)*2+3

其实当m=3的时候还可以递推，不过官方分类是dp。。。只好用一点啊。

#include <stdio.h>
int a[4][1000005]={0};
int main ()
{
	int n,m,i,j;
	for (i=0;i<1000001;i++)
	   a[0][i]=i+1;
	for (i=0;i<1000001;i++)
	   a[1][i]=i+2;
	for (i=0;i<1000001;i++)
	   a[2][i]=i+i+3;
	a[3][0]=5;
	for (i=1;i<25;i++)
	   a[3][i]=2*a[3][i-1]+3;
	while (scanf("%d %d",&m,&n)!=EOF)
	   printf ("%d/n",a[m][n]);
	return 0; 
}