Day2 - 美丽序列

1.题目描述

链接：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取模

输入描述

第一行输入一个整数n (1 ≤ n ≤ 40)
第二行输入n个整数

输出描述

输出一个整数

2.示例

输入：

3
5 3 -1

输出：

3.思路分析

我们注意到数字的状态和题目条件：

对于第i个数，可能取值为 j （numbers[i] 为-1的话），每个数在0-40之间，因此 0<=j<=40;
没有三个连续的递减的数，因此第i个数只有可能是第一个递减的数或者第二个递减的数（否则不存在美丽序列），因此可以用一个k来表示递减的状态（也就是第几个）
每个数要小于等于之前数的平均值，因此需要对前面数的和/均值进行记录和判断

结合上述的分析，可以设计动态规划数组：dp[i][j][k][sum]表示第i个位置，取值为 j 时，递减状态为k，和为sum的方案数

k只能取值为 1 或者 2

初始化

初始化的时候对第一个number进行判断即可，如果第一个number为 -1，遍历初始化dp[0][j][1][j] = 1; 其中 0<=j<=40;否则直接初始化dp[0][number][1][number] = 1;

那么状态转移如下：

1.当numbers[i]不为-1的时候，对递减进行判断

如果当前的值大于上一个值（numbers[i] >= lj）：

dp[i][numbers[i]][1][sum+numbers[i]] += dp[i-1][lj][1][sum]+dp[i-1][lj][2][sum];

sum为前i-1个数字的和，lj为上一个数字的值(last j)

否则，

dp[i][numbers[i]][2][sum+numbers[i]] += dp[i-1][j][1][sum];

2.当numbers[i]为-1的时候，我们只需要对j进行遍历，和lj进行比较即可(多加一层循环）

如果当前取的j值大于上一个值 (j>= lj ):

dp[i][j][1][sum+j] += dp[i-1][lj][1][sum]+dp[i-1][lj][2][sum];

否则，

dp[i][j][2][sum+j] = dp[i-1][lj][1][sum];

4.代码实现

#include<iostream>
#include<vector>
using namespace std;


//dp[i][j][k][sum]表示第i个位置的数为j时，递减为第k位，总和为sum的方案数
//dp[i][j][k][sum]
long long dp[41][41][3][1601];
int numbers[40];
const int MOD = 1e9 + 7;

int main()
{

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> numbers[i];
	//初始化dp数组
	if (numbers[0] == -1)
	{
		for (int j = 0; j <= 40; ++j)
			dp[0][j][1][j] = 1;
	}
	else
	{
		dp[0][numbers[0]][1][numbers[0]] = 1;
	}
	//进行状态转移
	for (int i = 1; i < n; ++i)
	{
		if (numbers[i] == -1)
		{
			//枚举这个-1可能取得的值
			for (int j = 0; j <= 40; ++j)
			{
				//枚举上一个数
				for (int lj = 0; lj <= 40; ++lj)
				{
					//枚举之前的和，大于平均值
					for (int s = j * i; s <= 40 * i; ++s)
					{
						if (j >= lj)
						{
							dp[i][j][1][s + j] += dp[i - 1][lj][1][s] + dp[i - 1][lj][2][s];
							dp[i][j][1][s + j] %= MOD;
						}
						else
						{
							dp[i][j][2][s + j] += dp[i - 1][lj][1][s];
							dp[i][j][2][s + j] %= MOD;
						}
					}
				}
			}
		}
		else
		{
			//枚举上一个数，可能是 0-40 中的一位
			for (int lj = 0; lj <= 40; ++lj)  
			{
				//枚举之前的和，满足大于平均值
				for (int s = numbers[i] * i; s <= 40 * i; ++s)
				{
					if (numbers[i] >= lj)
					{
						dp[i][numbers[i]][1][s + numbers[i]] += dp[i - 1][lj][1][s] + dp[i - 1][lj][2][s];
						dp[i][numbers[i]][1][s + numbers[i]] %= MOD;
					}
					else
					{
						dp[i][numbers[i]][2][s + numbers[i]] += dp[i - 1][lj][1][s];
						dp[i][numbers[i]][2][s + numbers[i]] %= MOD;
					}
				}
			}
		}
	}
	//查找答案
	long long res = 0;
	for (int j = 0; j <= 40; ++j)
	{
		for (int s = j * n; s <= 1600; ++s)
		{
			res = res + dp[n-1][j][1][s] + dp[n-1][j][2][s];
			res %= MOD;
		}
	}
	printf("%lld", res);

	return 0;
}