美丽序列

题意:
牛牛喜欢整数序列，他认为一个序列美丽的定义是
1：每个数都在0到40之间
2：每个数都小于等于之前的数的平均值
具体地说：for each i, 1 <= i < N, A[i] <= (A[0] + A[1] + ... + A[i-1]) / i.
3：没有三个连续的递减的数
现在给你一个序列，每个元素是-1到40，你可以将序列中的-1修改成任意的数，求你可以得到多少个美丽序列，答案对1e9+7取模.
对于题目我们很容易想到第一维是到了第几个数.对于第二个条件,我们就得想到前面的总和是多少,到了第三个条件我们就得设当前是递减序列的第几个,为了方便转移我们还需要另设一个就是当前的值是多少.总体而言dp的状态就是dp[i][j][l][k],表示到了第i个数值是j位于递减序列中的第l个总和为k的数列有多少.那么代码就很容易了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=45,M=1605,L=3;
const ll mod=1e9+7;
ll a[N];
ll dp[N][N][L][M];
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    if(a[1]==-1)
    {
       for(ll i=0;i<=40;i++) dp[1][i][1][i]=1;
    }
    else dp[1][a[1]][1][a[1]]=1;
    for(ll i=2;i<=n;i++)//到了第几个.
    {
        if(a[i]==-1)//不确定.
        {
            for(ll j=0;j<=40;j++)//枚举当前哪个数.
            {
                for(ll lj=0;lj<=40;lj++)//枚举上个数是哪个数.
                {
                    for(ll k=j*(i-1);k<=1600-j;k++)//枚举可行的sum
                    {
                        if(j>=lj)//假设我当前值大于上一个的值.
                        {
                            dp[i][j][1][k+j]=(dp[i][j][1][k+j]+dp[i-1][lj][1][k]+dp[i-1][lj][2][k])%mod;
                        }
                        else
                        {
                            dp[i][j][2][k+j]=(dp[i][j][2][k+j]+dp[i-1][lj][1][k])%mod;
                        }
                    }
                }
            }
        }
        else//确定.
        {
            for(ll lj=0;lj<=40;lj++)//枚举上个数是哪个数.
                {
                    for(ll k=a[i]*(i-1);k<=1600-a[i];k++)//枚举可行的sum
                    {
                        if(a[i]>=lj)//假设我当前值大于上一个的值.
                        {
                            dp[i][a[i]][1][k+a[i]]=(dp[i][a[i]][1][k+a[i]]+dp[i-1][lj][1][k]+dp[i-1][lj][2][k])%mod;
                        }
                        else
                        {
                            dp[i][a[i]][2][k+a[i]]=(dp[i][a[i]][2][k+a[i]]+dp[i-1][lj][1][k])%mod;
                        }
                    }
                }
        }
    }
    ll ans=0;
    for(ll j=0;j<=1600;j++)
    {
        for(ll i=0;i<=40;i++)
        {
            ans=(ans+dp[n][i][1][j])%mod;
            ans=(ans+dp[n][i][2][j])%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}