hdu 1028 Ignatius and the Princess III

这题题目很简单，但是看了discuss之后发现，各种神牛的解法，很值得学习。

在此写个结题报告

解法一：

ps：这个是我自己的做法，直接递推，时间复杂度15ms水过的

#include<stdio.h>
int ans[130];
int main()
{
    int i,j,k,n;
    ans[0]=1;
    for(i=1;i<=120;i++)
    {
        for(j=0;j+i<=120;j++)
            ans[j+i]+=ans[j];
    }
    while(scanf("%d",&n)!=-1)
        printf("%d\n",ans[n]);
    return 0;
}

方法二：记忆化搜索，也是个不错的想法

可以这样考虑将，n构造为非递增子序列的和一共有多少个这样的序列。假设一个状态，起一个元素的为last，现在需要分配的剩余数为n。所以一开始状态应该为fun(n,last)。下一步只需要继续构造非递增子序列一直到n为1。用记忆搜索实现：

#include<stdio.h>
#include<string.h>
const int MAX = 121 ;
int count = 0 ;
int vis[MAX][MAX] ;
int fun(int n ,int last)
{
	
	if(n <= 1)
	{
		return 1;
	}
	
	if(vis[n][last] > 0)
	{
		return vis[n][last] ;
	}
	
	int sum = 0 ;
	for(int i = n ; i >= 1 ; i--)
	{
		if(i <= last)
		{
			vis[n-i][i] = fun(n-i ,i) ;
			sum += vis[n-i][i] ;
		}
	}
	return sum ;
}

int main()
{
	int n;
	while(~scanf("%d" , &n))
	{
		count=0;
		memset(vis , 0 , sizeof(vis)) ;
		printf("%d\n" , fun(n,n)) ;
	}
	return 0 ;
}

方法三：用矩阵

这个方法一般很难想到。用了个二维数组。

用这个方法0ms就能过，其实说白了就是记忆化搜索，和方法二理念类似。

#include<stdio.h>
main()
{int a[122][122],n,i,j;
for(i=0;i<121;i++)
{a[i][0]=1;a[i][1]=1;a[0][i]=1;a[1][i]=1;}
for(i=2;i<121;i++)//第一维i表示“被拆的数”的大小，第二维j表示“被拆成的数”里面最大的数
for(j=2;j<121;j++)
 if(i>=j)a[i][j]=a[i][j-1]+a[i-j][j];
else   a[i][j]=a[i][i];
while(scanf("%d",&n)==1)
printf("%d\n",a[n][n]);
}