Problem Link

题目大意

给定 $n$ 个盒子，第 $i$ 个盒子容量为 $a_i$，然后依次给出 $m$ 个球，第 $i$ 个球可以放到 $p_i$ 或 $p_i+1$ 号盒子，如果两个盒子都满了就丢弃，求最多能丢弃多少个球。

数据范围：$n,m\le 8000$。

思路分析

首先我们枚举每个盒子在哪个时刻满了，记为 $t_i$，那么一个球被丢弃当且仅当 $i>\max(t_{p_i},t_{p_i+1})$。

考虑什么样的一组 $t_i$ 是合法的。

可以用二分图最大匹配问题刻画，左部是所有盒子的容量，右部连接能放到这个盒子里的球。

用 Hall 定理判定，显然我们只要考虑若干连续的盒子 $[l,r]$，能放到这些盒子里的球个数必须 $\ge\sum_{i=l}^r a_i$。

可以把这个问题看成一个类似最小子段和的问题，动态维护后缀最小值就能判定。

那么就有一个朴素 dp：$dp_{i,j,k}$ 表示前 $i$ 个盒子，$t_i=j$，且当前后缀最小值为 $k$ 的方案数。

注意到 $j$ 一定是某个 $p_x\in\{j-1,j\}$ 的 $x$，设这样的 $x$ 总数为 $s_i$，则 $k\le s_i-a_i$。

所以状态总数 $\le \sum s_i^2=\mathcal O(m^2)$。

转移时就枚举 $j'$ 算出 $(j,k)\to (j',k')$ 的系数，此时复杂度 $\mathcal O(m^3)$。

注意特殊处理 $j=\infty$ 的情况，此时这个点不在二分图中，不能考虑过这个点的区间。

判掉这种特殊情况，发现转移只在 $j'<j$ 和 $j\le j'$ 两种情况有较大区别，对于这两部分都能轻松地优化到 $\mathcal O(m^2)$。

时间复杂度 $\mathcal O(nm+m^2)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=8005,inf=1e9;
int n,a[MAXN],m,p[MAXN],s[MAXN],ct[MAXN],w[MAXN];
vector <int> b[MAXN];
vector <vector<int>> dp,f,g,nw;
inline void chkmax(int &x,const int &y) { x=y>x?y:x; }
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],b[i].push_back(0);
	cin>>m;
	for(int i=1;i<=m;++i) cin>>p[i],b[p[i]].push_back(i),b[p[i]+1].push_back(i);
	for(int i=1;i<=n;++i) s[i]=b[i].size()-1,a[i]=min(a[i],s[i]);
	dp=vector<vector<int>>(s[1]-a[1]+1,vector<int>(s[1]-a[1]+1,-inf));
	for(int j=a[1];j<=s[1];++j) dp[j-a[1]][j-a[1]]=0;
	for(int i=2;i<=n;++i) {
		for(int j=1;j<=m;++j) ct[j]=ct[j-1]+(p[j]==i-1);
		for(int j=a[i-1];j<=s[i-1];++j) {
			w[j]=upper_bound(b[i].begin(),b[i].end(),b[i-1][j])-b[i].begin();
			w[j]=min(max(w[j],a[i]),s[i]);
		}
		nw=g=vector<vector<int>>(s[i]-a[i]+1,vector<int>(s[i]-a[i]+1,-inf));
		f=vector<vector<int>>(s[i]-a[i]+1,vector<int>(s[i-1]-a[i-1]+1,-inf));
		for(int j=a[i-1];j<=s[i-1];++j) for(int k=0;k<=s[i-1]-a[i-1];++k) {
			const int &z=dp[j-a[i-1]][k];
			if(z<0) continue;
			if(j==s[i-1]) { //j = inf
				for(int t=a[i];t<=s[i];++t) {
					chkmax(nw[t-a[i]][t-a[i]],z+ct[m]-ct[max(b[i-1][j],b[i][t])]);
				}
			} else {
				chkmax(nw[s[i]-a[i]][0],z+ct[m]-ct[max(b[i-1][j],b[i][s[i]])]); //j' = inf, k = any val
				if(a[i]<w[j]) chkmax(f[w[j]-a[i]-1][k],z+ct[m]-ct[b[i-1][j]]);
				if(w[j]<s[i]&&-min(0,k-ct[b[i-1][j]])<=s[i]-a[i]) {
					chkmax(g[w[j]-a[i]][-min(0,k-ct[b[i-1][j]])],z);
				}
			}
		}
		for(int t=a[i];t<s[i];++t) for(int x=0;x<=s[i]-a[i];++x) {
			if(t>a[i]) chkmax(g[t-a[i]][x],g[t-a[i]-1][x]);
			int mn=-x+t-a[i];
			if(mn>=0) chkmax(nw[t-a[i]][mn],g[t-a[i]][x]+ct[m]-ct[b[i][t]]);
		}
		for(int t=s[i]-1;t>=a[i];--t) for(int k=0;k<=s[i-1]-a[i-1];++k) {
			chkmax(f[t-a[i]][k],f[t-a[i]+1][k]);
			int mn=min(0,k-ct[b[i][t]])+t-a[i];
			if(mn>=0) chkmax(nw[t-a[i]][mn],f[t-a[i]][k]);
		}
		dp.swap(nw);
	}
	int ans=0;
	for(int j=a[n];j<=s[n];++j) for(int k=0;k<=s[n]-a[n];++k) chkmax(ans,dp[j-a[n]][k]);
	cout<<ans<<"\n";
	return 0;
}