NKOJ 3051 浇花 （差分数组/区间DP）

发表于 |
字数统计: 1,512字 | 阅读时长 ≈ 7min

P3051浇花

问题描述

n 个非负整数排成一行，每个数值为Ai，数的位置不可改变。需要把所有的数都恰好等
于h。可进行的操作是：对任意长度的区间[i,j]中的每个数都加1，i 和j 也任选，但要求每
个数只能作为一次区间的起点，也只能作为一次区间的终点。也即是说： 对任意的两个区
间[l1, r1] 和[l2, r2], 要求: l1≠l2 并且r1 ≠ r2.
请问有多少种不同的方式，使所有的数都等于h.输出答案模1000000007 (10^9+7)后的
余数。
两种方式被认为不同，只要两种方式所实施的操作的区间集合中，有一个区间不同即可.

输入格式

第1 行：2 个整数n, h (1 ≤ n, h ≤ 2000)
接下来n 行，每行1 个整数，表示Ai (1≤Ai≤2000)
30%的数据，n, h <= 30
100%的数据，n, h <= 2000

输出格式

第1 行：1 个整数，表示答案

样例输入

Sample1:
3 2
1 1 1
Sample2:
5 1
1 1 1 1 1

样例输出

Sample1:
4
Sample2:
1

此题有两种做法。
做法一：比较笨拙的DP做法

引用一下考试时的题解

类似于括号dp的讨论方式，讨论i的左边，选哪个数字作为区间的起点，更新i的值

dp[i][k]表示从左往右讨论到第i个数字，i的左边有k个数字还未被用过(被当做区间的左起点), 的方案数。

分两种情况讨论：

情况1：i被别人更新(因为i前面的k个数，任选一个为区间起点，都可更新到i)：

若a[i]+k==h 则dp[i][k]=dp[i+1][k-1]*k+dp[i+1][k]

说明，条件a[i]+k==h,因为i左边有k个数字还没用过，那么以这k个数字作为区间左起点可以操作k次，每次都可以更新到i，更新k次，恰好就能使a[i]变成h。

现在对于i而言，有两种选择， 使用i或者不使用i。

若用i作为区间右端点，因为i只能当一次区间终点，所以只能从前k个中选一个来与它配对，故有k种方案，k个数中i选了一个，对于i+1它左边就只有k-1个未使用的数了，数量总数为k*dp[i+1][k-1] 。

注意，这里i不能再作为区间的左端点了，这样的话会导致i被多更新一次，高度变成h+1

若不用i作为区间端点，则方案数为dp[i+1][k]

情况2：i作为区间起点去更新别人

若a[i]+k+1=h则dp[i][k]=dp[i+1][k]*(k+1)+dp[i+1][k+1]

说明，因为i前面有k个数未被当做左起点使用，全部操作都只能把a[i]更新到h-1这个高度，那么i号点必须自己作为某区间的左起点更新一次，在更新这个区间的同时把自己的高度也更新1，达到h。

这样，对于下一个数i+1而言，算上i号点，它左侧有k+1个点可选做区间左端点，任选一个选后剩下k个点，状态dp[i+1][k]

若不用i作为区间左端点，则方案数为dp[i+1][k+1]

时间复杂度O(n2),实现时采用记忆化搜索比较方便。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll n,h,A[2222],F[2222][2222],mod=1000000007;
ll DFS(ll x,ll k)
{
	if(F[x][k]!=-1)return F[x][k];
	if(x==n+1)
	{
		if(k==0)return 1;
		else return 0;
	}
	F[x][k]=0;
	if(A[x]+k==h)F[x][k]=DFS(x+1,k-1)*k%mod+DFS(x+1,k);
	if(A[x]+1+k==h)F[x][k]=DFS(x+1,k)*(k+1)%mod+DFS(x+1,k+1);
	F[x][k]%=mod;
	return F[x][k];
}
int main()
{
	ll i;
	scanf("%lld%lld",&n,&h);
	for(i=1;i<=n;i++)scanf("%lld",&A[i]);
	memset(F,-1,sizeof(F));
	printf("%lld",DFS(1,0)%mod);
}

做法二：优秀的差分数组解法

首先将题目中的数组中每个数变成$H-A[i]$得到新的$A[i]$。
然后将数组$A[i]$差分一下记作$B[i]$，那么先判无解。

首先，如果存在$A[i]>H$那么显然无解。
然后，如果$B[i]$中存在除了$1,0,-1$以外的数，那么无解。
（证明：反向考虑，如果存在解，那么每次区间修改都会在差分数组中的两个位置+1或-1，那么由于每个位置只能做一次起点和终点，+1和-1的次数最多都只有一次，所以必然$B[i]$中只有1,0，-1）

之后就可以考虑成类似括号匹配的问题。
由于差分数组的原理，那么每一个1都要和-1配对，用$cnt$表示讨论到$i$位置时，左边还没有配对的1。

如果$i$位置是1，那么$cnt++$即可。
如果$i$位置是-1，那么他可以和左边任意一个1配对，$ans=ans\times cnt$，然后$cnt–$
如果$i$位置是0，那么$i$位置可能没有操作，对方案没有影响，或者$i$位置可以看成一个1和-1，既是起点又是终点，那么先$cnt++$，然后$ans=ans\times cnt$，之后$cnt–$，等价于$ans=ans\times (cnt+1)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll i,n,h,ans,cnt,A[2222],B[2222],mod=1e9+7;
int main()
{
	scanf("%lld%lld",&n,&h);ans=1;
	for(i=1;i<=n;i++)scanf("%lld",&A[i]),A[i]=h-A[i];
	for(i=1;i<=n+1;i++)B[i]=A[i]-A[i-1];
	for(i=1;i<=n+1;i++)
	{
		if(B[i]==1)cnt++;
		else if(B[i]==0)ans=ans*(cnt+1)%mod;
		else if(B[i]==-1)ans=ans*cnt%mod,cnt--;
		else {ans=0;break;}
	}
	cout<<ans;
}