HDU-7304 2023“钉耙编程”杭电多校赛（3）Out of Control

2023“钉耙编程”中国大学生算法设计超级联赛（3）Out of Control

题目大意

有 n n n个数 x 1 , x 2 , … , x n x_1,x_2,\dots,x_n x1​,x2​,…,xn​，在其中选 k k k个数依次放入栈中。如果当前放入栈中的数 x i x_i xi​小于栈顶的数，则向栈中放入与先前的栈顶相同的数而不是 x i x_i xi​。

对于每一个 i ∈ [ 1 , n ] i\in[1,n] i∈[1,n]，求 k = i k=i k=i时不同栈的数量。

有 T T T组数据。

1 ≤ T ≤ 100 , 1 ≤ n ≤ 3000 1\leq T\leq 100,1\leq n\leq 3000 1≤T≤100,1≤n≤3000

题解

将 x i x_i xi​从小到大排序，那么一组可能的栈 s 1 , s 2 , … , s k s_1,s_2,\dots,s_k s1​,s2​,…,sk​合法当且仅当 s s s中仅包含 x x x中的数，且对于所有的 1 ≤ i ≤ k 1\leq i\leq k 1≤i≤k都要满足 s i ≥ x i s_i\geq x_i si​≥xi​。

我们先将 x i x_i xi​离散化一下。考虑 D P DP DP。设 f i , j f_{i,j} fi,j​表示合法的长度为 i i i的满足 s i = j s_i=j si​=j的序列 s s s的数量，那么状态转移式为

f i , j = ∑ k = 1 j f i − 1 , k f_{i,j}=\sum\limits_{k=1}^jf_{i-1,k} fi,j​=k=1∑j​fi−1,k​

其中 j ≥ x i j\geq x_i j≥xi​。

可以用前缀和来优化 D P DP DP。

时间复杂度为 O ( ∑ n 2 ) O(\sum n^2) O(∑n2)。

code

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int t,n,a[3005],num[3005];
long long sum,ans,f[3005][3005];
int main()
{
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			num[i]=a[i];
		}
		sort(num+1,num+n+1);
		int vt=unique(num+1,num+n+1)-num-1;
		for(int i=1;i<=n;i++){
			a[i]=lower_bound(num+1,num+vt+1,a[i])-num;
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=vt;i++){
			f[1][i]=1;
		}
		printf("%d\n",vt);
		for(int i=2;i<=n;i++){
			sum=ans=0;
			for(int j=a[i-1];j<a[i];j++) sum=(sum+f[i-1][j])%mod;
			for(int j=a[i];j<=vt;j++){
				sum=(sum+f[i-1][j])%mod;
				f[i][j]=sum;
				ans=(ans+f[i][j])%mod;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}