链接：https://ac.nowcoder.com/acm/problem/21313
来源：牛客网
题目描述
牛牛喜欢整数序列，他认为一个序列美丽的定义是
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取模
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个整数
输出描述:
输出一个整数
示例4
输出
复制579347890
思路：类似牛牛和数组那一题。此题添加了另外两个限制。因此开了四维数组。
#include <cstdio> #include <cstdlib> #include <climits> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #include <iostream> using namespace std; typedef long long ll; const int mod = 1e9+7; const double PI=3.14159265358; const int INF=0x3f3f3f3f; int n; //储存输入的数组 ll a[42]; //dp开四维数组:dp[i][j][k][h]; //分别对应第i层，值为j，是递减序列中的第k个，且i层数组的前i个数的和是h; //把整数序列当成一个数组。所以i表示数组的长度 //因为数组中每个数的范围是0~40，所以j表示0~40. //因为要求没有三个连续的递减的数。所以用k表示这个数在数组中是三个递减数的第一个。还是第二个 //因为每个说都小于之前的数的平均数。所以用h表示在数组中从第一个直到第i个数的总和。 ll dp[41][41][3][1610]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } memset(dp,0,sizeof(dp)); //判断第一个数,由于是第一个数，所以他只能是递减序列的第一个 if(a[1]==-1){ //由于是-1所以，第一个数可以是0~40中的任一一个数 for(int i=0;i<=40;i++){ //第1层值为i且是递减序列中第一个的且总和为i的可能性为1; dp[1][i][1][i]=1; } }else{ //第1层值为a[i]且是递减序列中第一个的且总和为a[i]的可能性为1; dp[1][a[1]][1][a[1]]=1; } //从第二层往后推 for(int i=2;i<=n;i++) { if(a[i]==-1){ //第i层的数可以是0~40.用j表示 for(int j=0;j<=40;j++){ //循环第i-1层的值是0~40.用l表示 for(int l=0;l<=40;l++){ //k表示到目前这一层的总和的值。 //由于小于等于前i-1层的数的总和的平均数。 //所以用j乘以i-1层表示k的最小值。 //最大值是40*40减去当前这一层的值。 for(int k=j*(i-1);k<=1600-j;k++) { //如果j>=l:表示这一层的值可以作为递减序列的第一个 if(j>=l){ //用第i层值为j的。且位于递减序列的第一个的。且总和为k+j的dp //加上上一层的值为0~40.且位于递减序列的第一个和第二个的。且总和为k //的dp相加。 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{ //如果j<l。表示这个数只能是递减序列的第二个。 //第i层值为j的。且位于递减序列的第二个的。且总和为k+j的dp //加上上一层的值为0~40.且位于递减序列的第一个。且总和为k的dp。 dp[i][j][2][k+j]=(dp[i][j][2][k+j]+dp[i-1][l][1][k])%mod; } } } } }else{ //类似上面的情况。不过是把j确定为a[i]了 for(int l=0;l<=40;l++){ for(int k=a[i]*(i-1);k<=1600-a[i];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; } } } } } ll ans=0; //循环当前n层的值为0~40的所有可能情况。 for(int i=0;i<=40;i++){ //循环所有可能和的情况。将k设置=i*n。是为了简便计算 for(int k=i*n;k<=1600;k++){ //需要累加位于递减序列的第一个和第二个的两种情况的dp的和。 ans=(ans+dp[n][i][1][k])%mod; ans=(ans+dp[n][i][2][k])%mod; } } cout<<ans<<endl; return 0; }