signed

QiShunwang

“诚信为本、客户至上”

洛谷P4933 大师(动态规划)

2021/6/24 17:23:43   来源:

题目链接:https://www.luogu.com.cn/problem/P4933

设电塔高度数组为h[1...n].

状态表示:

dp[i][k]表示以第i个数结尾(必须包含)的公差为k长度大于1的等差数列的数目。

由于k的可能取值仅与i前面的数据相关,因此只需要枚举j(j<i)就可以了。

状态计算dp[i][h_{i}-h_{j}]=dp[j][h_{i}-h_{j}]+1+dp[i][h_{i}-h_{j}]

含义:长度大于2的数列数目是以a_{j}结尾的数列拼上a_{i}之后的数列的数目:dp[j][h_{i}-h_{j}]

长度为2的数列:a_{j}a_{i}形成的数列,方案数目为1.

为了方便最后答案的累加,引入数组sum[i]表示以i结尾的数列的数目,那么

sum[i]=(\sum dp[i][k])+1,含义就是长度大于1的等差数列的数目加上只有a_{i}一项的方案数。计算sum[i]可以通过枚举k的可能取值去计算(k的最大范围:[-40000,40000]),但是其实没有必要,因为不是这么大范围的k都有可能作为公差,所以简化为:

sum[i]=\left \{ \sum_{j=1}^{i-1}(dp[j][h_{i}-h_{j}]+1) \right \}+1

额外注意点由于公差可正负,因此具体实现时可以将所有的d整体向右偏移一个合理大的常数(如20005),当然也可以将dp数组拓展一个维度,比如dp[i][abs(k)][1]代表长度大于1不减等差数列的数目,dp[i][abs(k)][0]代表长度大于1的递减等差数列的数目。最后说明:其实ans的计算也可以直接放在dp计算过程中,这样子sum数组就可以省去。

#include<bits/stdc++.h>
using namespace std;
const int N = 1001;
#define mod 998244353
int dp[N][40005], h[N], sum[N];
int n;

int main()
{
	cin>>n;
	for(int i = 1;i <= n; i++)cin>>h[i];
	
	for(int i = 1;i <= n; i++)
	{
		sum[i] = 1;
		for(int j = 1;j < i; j++)
		{
			int d = h[i] - h[j] + 20005;
			dp[i][d] = ( dp[j][d] + 1 + dp[i][d] )%mod;
			sum[i] = (sum[i] + dp[j][d] + 1)%mod;
		}
	}
	
	int ans = 0;
	for(int i = 1;i <= n; i++)
	{
		ans = ( ans + sum[i] )%mod;
	}
	
	cout<<ans;
	return 0;
}