题意
福克斯喜欢整数序列，他认为一个序列美丽的定义是
1.每个数都在(0)到(40)之间
2.每个数都小于等于之前的数的平均值
具体地说：
for each (i,1le i<N,A[i]le (A[0]+A[1]+...+A[i-1])/i).
3.没有三个连续的递减的数
现在给你一个序列，每个元素是(-1)到(40)，你可以将序列中的(-1)修改成任意的数，求你可以得到多少个美丽序列，答案对(1e9+7)取模
输入格式
第一行输入一个整数(n(1le nle 40))
第二行输入(n)个整数
输出格式
输出一个整数
样例输入1
2
3 -1
样例输出1
4
样例输入2
3
5 3 -1
样例输出2
2
样例输入3
3
-1 0 40
样例输出3
0
样例输入4
11
-1 40 -1 -1 -1 10 -1 -1 -1 21 -1
样例输出4
579347890
样例输入5
6
-1 12 25 0 18 -1
样例输出5
58
分析
不想贪心，暴力dp即可。
因为数据范围极小，所以开四维dp数组，(dp[i][last][len][sum])表示第(i)个数是(last)，前(i)个数组成的序列末尾的递减序列长度为(len)，前(i)个数的和为(sum)，则转移方程：（前缀(new)表示当前状态，不加表示上一个状态）
(if;i>1;then{)
(if;a[i]!=-1;then)
(dp[i][a[i]][2][newsum]=sum dp[i-1][last][1][sum])
(dp[i][a[i]][1][newsum]=sum dp[i-1][last][2][sum]+sum dp[i-1][last][1][sum])
(else)
(dp[i][newlast][2][newsum]=sum dp[i-1][last][1][sum])
(dp[i][newlast][1][newsum]=sum dp[i-1][last][2][sum]+sum dp[i-1][last][1][sum])
(})
(else{)
(if;a[1]!=-1;then)
(dp[1][a[1]][1][a[1]]=1)
(else)
(dp[1][last][1][last]=1)
(})
Code
#include<cstdio>
#define maxn 45
#define mod 1000000007ll
#define PE(x,y) x=((x)+(y))%mod
using namespace std;//dp[i][num_at_the_end][length_of_decreasing_sequence][sum]
int a[maxn],n;
long long dp[maxn][maxn][3][1605];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
if(a[1]!=-1)dp[1][a[1]][1][a[1]]=1;
else{
for(int last=0;last<=40;last++){
dp[1][last][1][last]=1;
}
}
for(int i=2;i<=n;i++){
if(a[i]!=-1){
for(int sum=a[i]*(i-1);sum<=1600-a[i];sum++){
int newsum=sum+a[i];
for(int last=0;last<=40;last++){
if(a[i]<last){
PE(dp[i][a[i]][2][newsum],dp[i-1][last][1][sum]);
}
else{
PE(dp[i][a[i]][1][newsum],dp[i-1][last][2][sum]);
PE(dp[i][a[i]][1][newsum],dp[i-1][last][1][sum]);
}
}
}
continue;
}
for(int newlast=0;newlast<=40;newlast++){
for(int sum=newlast*(i-1);sum<=1600-a[i];sum++){
int newsum=sum+newlast;
for(int last=0;last<=40;last++){
if(newlast<last){
PE(dp[i][newlast][2][newsum],dp[i-1][last][1][sum]);
}
else{
PE(dp[i][newlast][1][newsum],dp[i-1][last][2][sum]);
PE(dp[i][newlast][1][newsum],dp[i-1][last][1][sum]);
}
}
}
}
}
long long ans=0;
for(int sum=0;sum<=1600;sum++){
for(int last=0;last<=40;last++){
for(int len=1;len<=2;len++){
PE(ans,dp[n][last][len][sum]);
}
}
}
printf("%lld",ans);
return 0;
}