美丽序列
题目描述 牛牛喜欢整数序列，他认为一个序列美丽的定义是 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取模 输入描述: 第一行输入一个整数n (1 ≤ n ≤ 40) 第二行输入n个整数 输出描述: 输出一个整数 示例1 输入 2 3 -1 输出 4 示例2 输入 3 5 3 -1 输出 2 示例3 输入 3 -1 0 40 输出 0 示例4 输入 11 -1 40 -1 -1 -1 10 -1 -1 -1 21 -1 输出 579347890 备注: 子任务1: n <= 10 子任务2: n <= 20 子任务3: 无限制
题目链接：https://ac.nowcoder.com/acm/problem/21313
解题思路：
按照动态规划的一般步骤 ， 假如 有个序列 ***** 5 我们需要知道 当前数与前一个数的大小关系 AC代码：
代码语言：javascript复制#include<string.h>
#include<iostream>
#define Mod 1000000007
using namespace std;
int main(){
int n;
long long a[42];
long long dp[42][42][3][1602];
// dp[i][j][1][k]代表当前 处理到第i个且值为j 在递减序列中第 1个前i个和为k
memset(dp,0,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i )cin>>a[i];
//初始化
if(a[1]==-1) {for(int i=0;i<=40;i )dp[1][i][1][i]=1;}
else dp[1][a[1]][1][a[1]]=1;
for(int i=2;i<=n;i ){
if(a[i]==-1){//若当前数为 -1 即可为任何数
for(int j=0;j<=40;j ){//枚举当前可能的数 0~40
for(int L=0;L<=40;L ){ //枚举当前前一个（i-1）可能的数 0~40
for(int k=j*(i-1);k<=1600-j;k ){//枚举前(i-1)个满足条件的和k
if(j>=L){//若当前大于前一个数 即打破递减序列的条件
dp[i][j][1][k j]=(dp[i][j][1][k j] dp[i-1][L][1][k])%Mod;
dp[i][j][1][k j]=(dp[i][j][1][k j] dp[i-1][L][2][k])%Mod;
}else dp[i][j][2][k j]=(dp[i][j][2][k j] dp[i-1][L][1][k])%Mod;
}
}
}
}else{//若为具体的大小
for(int L=0;L<=40;L ){//枚举上一个数的大小
for(int k=a[i]*(i-1);k<=1600-a[i];k ){//枚举前(i-1)个满足条件的和k
if(a[i]>=L){
dp[i][a[i]][1][k a[i]]=(dp[i][a[i]][1][k a[i]] dp[i-1][L][1][k])%Mod;
dp[i][a[i]][1][k a[i]]=(dp[i][a[i]][1][k a[i]] dp[i-1][L][2][k])%Mod;
}else dp[i][a[i]][2][k a[i]]=(dp[i][a[i]][2][k a[i]] dp[i-1][L][1][k])%Mod;
}
}
}
}
long long sum=0;
for(int j=0;j<=40;j ){//枚举 可能的大小
for(int k=j*n;k<=1600;k ){//枚举可能的和
sum=(sum dp[n][j][1][k])%Mod;
//当前数大小为j且在递减位置1 和为k的美丽序列数
sum=(sum dp[n][j][2][k])%Mod;
}
}
cout <<sum<<endl;
return 0;
}
