P1077 [NOIP2012 普及组] 摆花

这是我差不多是第一次从暴力递归优化到记忆化搜索，期间经历了一定的曲折。
解题过程：
1.看到这个题首先能够想到，每次摆花，可以选择和前面一样的花（如果前面的花还有剩余的话），也可以选择摆下一种花，于是最初的暴力递归算法就出来了。此方法提交有30分。

#include
#define MAX 101
using namespace std;
int n,m;
int num[MAX];//第i种花的数量
int res=0;
int sum(int temp)
{
    //剩余所有花的数量
    int all=0;
    for(int i=temp;i=m)
    {
        res+=1;
        res%=(1000007);
        return;
    }
    if(temp>=n||n-index>sum(temp))//如果当前选择花的序号已经超过了种类数，那么就停止
    {
        return;
    }
    if(num[temp]>0)
    {
        num[temp]-=1;
        fun(index+1,temp);
        num[temp]+=1;//注意回溯
    }
    fun(index,temp+1);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i>num[i];
    }
    fun(0,0);
    cout< 
2.将上述的暴力递归改为记忆化搜索，按照之前写的方法进行改动。提交后发现只有10分，原因在于：这里的变量还应该包含第temp种花的数量，因为前面使用到了回溯，记忆化之后无法将变量返回，所以要把这个变量也当成一个参数传入。得到第三个代码。
 
#include
#define MAX 101
using namespace std;
int n,m;
int num[MAX];//第i种花的数量
int res=0;
int arr[MAX][MAX];
void init()
{
    for(int i=0;i=m)
    {
        arr[index][temp]=1;
        return arr[index][temp];
    }
    if(temp>=n||n-index>sum(temp))
    {
        arr[index][temp]=0;
        return arr[index][temp];
    }
    int ways = 0;
    if(num[temp]>0)
    {
        num[temp]-=1;
        ways+=fun(index+1,temp);
        num[temp]+=1;
    }
    ways+=fun(index,temp+1);
    arr[index][temp]=ways;
    return arr[index][temp];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i>num[i];
    }
    init();
    int ways = fun(0,0);
    cout< 
3.将第temp种花的数量传入之后得到以下代码，注意方法要取余，不然只有50分：
 
#include
#define MAX 102
using namespace std;
int n,m;
int num[MAX];//第i种花的数量
int res=0;
int arr[MAX][MAX][MAX];
void init()
{
    for(int i=0;i=m)
    {
        arr[index][temp][num_temp]=1;
        return arr[index][temp][num_temp];
    }
    if(temp>=n||(n-index)>sum(temp,num_temp))//超过了n种花或者剩余所有花的总数都比要摆的花小
    {
        arr[index][temp][num_temp]=0;
        return arr[index][temp][num_temp];
    }
    long long ways = 0;
    if(num[temp]-num_temp>0)
    {
        ways+=(fun(index+1,temp,num_temp+1)%1000007);
        //num[temp]+=1;
    }
    ways+=(fun(index,temp+1,0)%1000007);
    ways%=1000007;
    arr[index][temp][num_temp]=ways;
    return arr[index][temp][num_temp];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i>num[i];
    }
    init();
    long long ways = fun(0,0,0);
    cout< 

 总结一下就是：要将所有的变量找齐，判断是哪些值在影响答案变化。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5635679.html