P1077 [NOIP2012 普及组] 摆花

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

#include<bits/stdc++.h>
#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<n;i++)
    {
    
        all+=num[i];
    }
    return all;
}
void fun(int index,int temp)//temp表示花的编号
{
    
    if(index>=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<n;i++)
    {
    
        cin>>num[i];
    }
    fun(0,0);
    cout<<res<<endl;
    return 0;
}

2.将上述的暴力递归改为记忆化搜索，按照之前写的方法进行改动。提交后发现只有10分，原因在于：这里的变量还应该包含第temp种花的数量，因为前面使用到了回溯，记忆化之后无法将变量返回，所以要把这个变量也当成一个参数传入。得到第三个代码。

#include<bits/stdc++.h>
#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<MAX;i++)
    {
    
        for(int j=0;j<MAX;j++)
        {
    
            arr[i][j]=-1;
        }
    }
}
int sum(int temp)
{
    
    //剩余所有花的数量
    int all=0;
    for(int i=temp;i<n;i++)
    {
    
        all+=num[i];
    }
    return all;
}
int fun(int index,int temp)
{
    
    if(arr[index][temp]!=-1)
    {
    
        return arr[index][temp];
    }
    if(index>=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<n;i++)
    {
    
        cin>>num[i];
    }
    init();
    int ways = fun(0,0);
    cout<<ways-2<<endl;
    return 0;
}

3.将第temp种花的数量传入之后得到以下代码，注意方法要取余，不然只有50分：

#include<bits/stdc++.h>
#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<MAX;i++)
    {
    
        for(int j=0;j<MAX;j++)
        {
    
            for(int k=0;k<MAX;k++)
            {
    
                arr[i][j][k]=-1;
            }

        }
    }
}
int sum(int temp,int num_temp)
{
    
    //剩余所有花的数量
    int all=num[temp]-num_temp;
    for(int i=temp+1;i<n;i++)
    {
    
        all+=num[i];
    }
    return all;
}
long long fun(int index,int temp,int num_temp)//num_temp表示使用了第temp号花多少盆
{
    
    if(arr[index][temp][num_temp]!=-1)
    {
    
        return arr[index][temp][num_temp];
    }
    if(index>=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<n;i++)
    {
    
        cin>>num[i];
    }
    init();
    long long ways = fun(0,0,0);
    cout<<ways<<endl;
    return 0;
}

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