首页 笔记 OI

# 前缀和优化

这个应该是最简单的一个一种 DP\text{DP} 优化吧。

当 DP\text{DP} 过程中需要反复从一个求和式转移的话，可以先把它预处理一下，运算一般满足可减性。

先搞个简单的练练手，熟悉一下吧。

# 逆序对数列

我们设 f[i][j]f[i][j] 表示 ii 的全排列中，逆序对数量为 jj 的个数。

那么我们只需要考虑在 i−1i-1 的排列中插入 ii ，会增加多少逆序对数，那再设 kk 为增加的逆序对数 (这里的 kk 与题目中的 kk 不一样), 就可以得到一下转移：

f[i][j]=∑k=0min(i−1,j)f[i−1][j−k]f[i][j]=\sum^{min(i-1,j)}_{k=0} f[i-1][j-k]

或者可以写成这样

f[i][j]=∑k=max(j−i−1,0)jf[i−1][k]f[i][j]=\sum^{j}_{k=max(j-i-1,0)}f[i-1][k]

Code
f[1][0]=1;
for(int i=2;i<=n;i++){
    for(int j=0;j<=K;j++){// 填完这一个位置后逆序对总数为 j
        for(int k=0;k<=min(i-i,j);k++){// 增加了多少
            f[i][j]+=f[i-1][j-k];
        }
    }
}

观察这个式子，发现 f[i][j]f[i][j] 其实是一段逆序对数为 jj 的一直到逆序对数位 j−i−1j-i-1 的方案数总和，所以我们可以用前缀和优化掉一维。

Code
for(int i=2;i<=n;i++){
        int summ=0;
        for(int j=0;j<=m;j++){
            summ=(summ+f[i-1][j])%mod;
            f[i][j]=summ;
            if(j>=i-1){
                summ=(summ-f[i-1][j-i+1]+mod)%mod;
            }
        }
    }

# 木棍分割

对于第一问还是很好做的，直接二分找出即可。对于第二问，我们可以想到设 f[i][j][k]f[i][j][k] 表示前 ii 根木棍 分成 jj 组，且最长的一组长为 kk。但会发现这 1≤k≤mid1 \leq k\leq mid，（这里的 midmid 就是第一问的答案）我们只需要在转移的时候让 kk 合法即可。所以就可以列出以下转移:

f[i][j]=∑l=ki−1f[l][j−1]这里的k是满足summ[i]−summ[k]≤mid的最小的位置f[i][j]=\sum^{i-1}_{l=k}f[l][j-1] \\ \text{这里的 $k$ 是满足$summ[i]-summ[k]\leq mid$的最小的位置}

观察式子，发现每次都是加上一段连续的序列，那么我们可以用前缀和优化啦。

记 sum[i][j]=∑k=0if[k][j]sum[i][j]=\sum^{i}_{k=0}f[k][j]

那么转移方程就又变成了这样: f[i][j]=sum[i][j−1]−sum[k−1][j−1]f[i][j]=sum[i][j-1]-sum[k-1][j-1]

发现 jj 这一维是只与该层以及上一层有关，直接滚掉 jj 这一维。

然后你根据以上思路交上代码会发现还有 TLE 的点，那是因为我们每次对与一个 ii 都在找满足 summ[i]−summ[k]≤midsumm[i]-summ[k]\leq mid 的最小的位置，这样很容易超时，所以我们用 pre[i]pre[i] 记一下对于位置 ii 所对应的 kk 的位置。

那么这道题目就解决啦。
✔️success

Code
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int MAXX=1e3+10;
const int mod=10007;
int a[MAXN];
int sum[MAXN],summ[MAXN],f[MAXN];
int pre[MAXN];
int n,m;
bool check(int mid){
	int summ=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]+summ>mid){
			cnt++;
			summ=a[i];
		}else{
			summ+=a[i];
		}
		if(cnt>m){
			return 0;
		}
	}
	return cnt<=m;
}
signed  main(){
    int l=0,r,ans,mid;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	sum[i]=sum[i-1]+a[i];
    	l=max(l,a[i]);
	}
	r=sum[n];
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	int k=0;
	for(int i=1;i<=n;i++){
		for(;k<i;k++){
			if(sum[i]-sum[k]<=ans){
				pre[i]=k;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(sum[i]<=ans){
			f[i]=1;
		}
		summ[i]=(summ[i-1]+f[i])%mod;
	}
	int anss=(sum[n]<=ans);
	for(int i=2;i<=m+1;i++){// 几组 
		for(int j=1;j<=n;j++){
			f[j]=summ[j-1];
			if(pre[j]-1>=0){
				f[j]=((f[j]-summ[pre[j]-1])%mod+mod)%mod;
			}
		}
		for(int j=1;j<=n;j++){
			summ[j]=(summ[j-1]+f[j])%mod;
		}
//		cout<<f[n]<<endl;
		anss=(anss+f[n])%mod;
	}
	cout<<ans<<" "<<anss;
}

# SAO

!! 这个题好 SAO！！

这种带有前置性的，并且根据数据范围能推出是一个树的，大概率是要用拓扑序了。

这个题其实就是让我们求解有多少种拓扑序而且题目中边方向的限制其实就是在限制拓扑序的前后，而且一般这种题目在设置 dpdp 状态的时都会考虑将拓扑序放到状态里，不然拓扑序就很难限制。

设 f[i][j]f[i][j] 表示以 ii 为根的字数， ii 在拓扑序中排第 jj 位的方案书，那么转移显然是合并子树，即:

f[u][i+j]+=f[u][i]×f[v][k]×Cf[u][i+j]+=f[u][i]\times f[v][k]\times C

因为我们不在乎除了 uu 和 vv 之外的点是怎么排的，所以得乘个组合数。考虑当合并子树时，对于 uu 的拓扑序，前面的 i−1i-1 个肯定还是存在的，那么当 vv 这个子树合并进来的时候，他的前面可能增加了 jj 个，所以我们要从合并之后的 uu 所在位置 i+ji+j 的前面的 i+j−1i+j-1 个位置中选出 i−1i-1 个位置，那么他的后面也是同理，我们就可以得到 CC 啦。

C=Ci+j−1i−1×Csiz[u]+siz[v]−i−jsiz[u]−iC=C_{i+j-1}^{i-1}\times C_{siz[u]+siz[v]-i-j}^{siz[u]-i}

以上都是把边当无向边做的，那么现在把他当有向边，这样无非就是规定了，uu 是在 vv 的左边还是右边，分类讨论即可。

当 uu 在 vv 的左边时：

for(int i=1;i<=siz[u];i++){
    for(int j=0;j<siz[v];j++){
        // 这里 0 是因为前面有可能一个都没有
		//< 是因为 v 在 u 后面，v 子树不可能全部都在 u 前面 
        for(int k=i+1;k<=siz[v];k++){
            f[u][i+j]+=f[u][i]*f[v][k]*C[i+j-1][i-1]*C[siz[u]+siz[v]-i-j][siz[u]-i];
        }
    }
}

当 uu 在 vv 的右边时：

for(int i=1;i<=siz[u];i++){
    for(int j=1;j<=siz[v];j++){
        for(int k=1;k<=j;k++){
            f[u][i+j]+=f[u][i]*f[v][k]*C[i+j-1][i-1]*C[siz[u]+siz[v]-i-j][siz[u]-i]
        }
    }
}

这个时候你发现又可以用前缀和优化啦，把 kk 那一维给优化掉。
所以把 ff 数组的定义给改一下， f[i][j]f[i][j] 表示在 ii 子树中它的拓扑序在 jj 及之前的方案数量的和。

Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <iomanip>
#define int long long
using namespace std;
const int mod=1e9+7;
const int MAXN=2e3+10;
struct edge{
	int nex,to,fla;
}p[MAXN];
int cnt,head[MAXN],siz[MAXN],f[MAXN][MAXN],c[MAXN][MAXN],f1[MAXN];
// 这里我直接用把 f 数组就当成方案数的前缀和了
//f1 当他的复制体
//c 的含义与上文讲解一样
void add(int from,int to,int fla){
//	cout<<fla<<endl;
	p[++cnt]=edge{head[from],to,fla};
	head[from]=cnt;
}
void dfs(int now,int fa){
	siz[now]=1;
	f[now][1]=1;
	for(int k=head[now];k;k=p[k].nex){
		int to=p[k].to;
		if(to==fa){
			continue;
		}
		dfs(to,now);
        // 注意到并入时用到的 f 值都应该是并入前的 f 值，所以要提前记录一下
		// 不然在转移时会受到影响 
		for(int j=1;j<=siz[now];j++){
			f1[j]=f[now][j]%mod;
			f[now][j]=0;
		}
		if(p[k].fla){
			for(int i=1;i<=siz[now];i++){
				for(int j=0;j<siz[to];j++){
					f[now][i+j]=(f[now][i+j]+(f[to][siz[to]]-f[to][j]+mod)%mod*f1[i]%mod*c[i+j-1][i-1]%mod*c[siz[now]+siz[to]-(i+j)][siz[to]-j]%mod)%mod;
				}
			}
        }else{
			for(int i=1;i<=siz[now];i++){
				for(int j=1;j<=siz[to];j++){
					f[now][i+j]=(f[now][i+j]+(f[to][j]*f1[i]%mod*c[i+j-1][i-1]%mod*c[siz[now]+siz[to]-(i+j)][siz[to]-j]%mod)%mod)%mod;
				}
			}
		}
		siz[now]+=siz[to];
	}
	for(int i=1;i<=siz[now];i++){
		f[now][i]=(f[now][i]+f[now][i-1])%mod;
	}
}
signed  main(){
	c[0][0]=1;
	for(int i=1;i<MAXN;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
		}
	}
    int t;
    cin>>t;
    while(t--){
    	int n;
    	cin>>n;
    	for(int i=1;i<n;i++){
    		int x,y;
    		char ch;
    		cin>>x>>ch>>y;
			x++,y++;
    		add(x,y,ch=='<');// 这是个好办法
    		add(y,x,ch=='>');
		}
		dfs(1,0);// 注意注意
                // 要是上面输入时没有自增 1，
                // 那么这里还是得填 dfs (1,n)
		printf("%lld\n",f[1][n]);
		for (int i=0;i<=n;i++)
		{
			for (int j=0;j<=n;j++) {
				f[i][j] = 0;
			}
			siz[i] = 0;
		}
        cnt=0;// 多测记得清零
        memset(head,0,sizeof(head));
        memset(p,0,sizeof(p));
	}
}

那么前缀和优化就 ✔️success 啦。

# 单调队列优化 （待续

更新于 阅读次数 次