题意

有 \(n\) 个景点，\(m\) 个望远镜，第 \(i\) 个望远镜的视野为 \([A_i,B_i]\) 中的景点，价格为 \(C_i\)。现在有 \(k\) 批游客，第 \(i\) 批游客有 \(Y_i-X_i+1\) 个人，分别愿意支付最多 \(X_i\sim Y_i\) 元钱。对于每个游客，你可以供给他一些可让他挑选的望远镜，他会选择能看到所有景点且不超过他愿意支付的最高钱数的花费最小的方案，求最大总收益。

题解

首先把 \(A,B\) 离散化，这样 \(n\) 就没用了。

其次不可能有两个望远镜的 \(A\) 或 \(B\) 相同，不然去掉视野范围更小的对游客更优。

再定睛一看数据范围，不难想到 dp。

设 \(dp_{i,j,k}\) 表示当前可以看到 \([1,i]\) 且去掉看到 \(i\) 的望远镜后可以看到 \([1,j]\)，花费为 \(k\) 的方案是否存在。

我们将所有望远镜按照 \(A\) 从小到大排序，如果 \(A\) 相等再按照 \(B\) 从大到小排序，原因在 dp 之后说明。

枚举望远镜 \(i\) 和去掉 \(i\) 后看到的最右景点 \(i1\)，转移 \(dp_{B_i,i1,k+C_i}=\oplus_{j=0}^{\max(A_i-1,1)-1}dp_{i1,j,k}\)，其中 \(\oplus\) 表示或运算。

为了使方案合法，即不存在从中去掉一个望远镜仍能看到同样大小视野或不能完全覆盖的情况，\(i1\) 的枚举范围应为 \([A_i-1,B_i-1]\)，\(j\) 的枚举范围应为 \([0,\max(A_i-1,1)-1]\)。\(i1\) 很好理解，\(j\) 是因为如果去掉看到 \(i1\) 的望远镜后最右景点为 \(j\) 且 \(j\ge A_i\)，那么用 \(j\) 和 \(i\) 两个望远镜就可以覆盖 \(i1\) 的视野，也就是说去掉 \(i1\) 对游客来说是更优的。至于为什么 \(A_i-1\) 要和 \(1\) 取 \(\max\)，是因为当 \(A_i\) 是 \(1\) 的时候如果不取 \(\max\) 就无法转移过来，或者理解成从 \(-1\) 转移过来，但是避免数组负数所以取 \(\max\)（也可以整体坐标 \(+1\)）。

了解了 dp 过程之后，现在解释一下为什么要这么排序。对于两个望远镜 \(i,j\)，如果它们的视野互不包含，那么它们之间是互相影响的，\(A\) 小的会对 \(A\) 大的产生影响，所以 \(A\) 要从小到大排序。至于 \(B\)，按理说顺序不要紧，但我们可以发现 dp 中并没有记录已经考虑了几个望远镜，所以说这就相当于背包问题中用了滚动数组，要从后往前考虑，因此 \(B\) 要从大到小排序。

dp 完之后，我们就可以知道哪些价格的方案是可行的，注意到对于一个游客价格最高只可能是 \(300\)，把 \(X,Y\) 缩小到这个范围，再预处理一下前缀和即可。

时间复杂度 \(O(\frac{Tm^4c}{\omega})\)，其中 \(c\) 是 \(C\) 的最大值 \(10\)，\(\omega\) 是 dp 过程 bitset 的优化，为 \(32\) 或 \(64\)。

Code

#include<cstdio>
#include<algorithm>
#include<bitset>
#define LL long long
using namespace std;
int n,m,k,m1,p_t,Mx,la,Test_num;LL ans;
int A[32],B[32],C[32],id[32],pre[302];
bitset<302> u;
bitset<302> dp[184][184];
struct aaa
{
	int val,id;
}p[184];
inline bool cmp(aaa a,aaa b)
{
	return a.val<b.val? 1:0;
}
inline bool cmp1(int a,int b)
{
	return (A[a]==A[b]? (B[a]>B[b]):(A[a]<A[b]));
}
int main()
{
	dp[0][0][0]=1,scanf("%d",&Test_num);
	for(int T=1;T<=Test_num;++T)
	{
		scanf("%d%d%d",&n,&m,&k),p_t=Mx=ans=la=0,u.reset(),m1=(m<<1);
		for(int i=1;i<=m;++i)scanf("%d%d%d",&A[i],&B[i],&C[i]),p[2*i-1]=(aaa){A[i],2*i-1},p[2*i]=(aaa){B[i],2*i},id[i]=i,Mx+=C[i];
		for(int i=1;i<=m;++i)
		{
			if(A[i]>1)p[++m1]=(aaa){A[i]-1,0};
			if(B[i]>1)p[++m1]=(aaa){B[i]-1,0};
			if(A[i]<n)p[++m1]=(aaa){A[i]+1,0};
			if(B[i]<n)p[++m1]=(aaa){B[i]+1,0};
		}
		p[++m1]=(aaa){1,0},p[++m1]=(aaa){n,0},sort(p+1,p+m1+1,cmp);
		for(int i=1;i<=m1;++i)
		{
			if(p[i].val!=p[i-1].val)++p_t;
			if(p[i].id)
			{
				if(p[i].id&1)A[(p[i].id+1)/2]=p_t;
				else B[p[i].id/2]=p_t;
			}
		}
		sort(id+1,id+m+1,cmp1);
		for(int i=1;i<=p_t;++i)
			for(int j=0;j<=p_t;++j)
				dp[i][j].reset();
		for(int i=1;i<=m;++i)
			for(int i1=A[id[i]]-1;i1<B[id[i]];++i1)
				for(int j=0;j<max(A[id[i]]-1,1);++j)
					dp[B[id[i]]][i1]|=(dp[i1][j]<<C[id[i]]);
		for(int i=0;i<=p_t;++i)
			for(int j=1;j<=Mx;++j)
				if(dp[p_t][i][j])
					u[j]=1;
		for(int i=1;i<=Mx;++i)
		{
			if(u[i])la=i;
			pre[i]=pre[i-1]+la;
		}
		for(int i=1,x,y;i<=k;++i)
		{
			scanf("%d%d",&x,&y),--x;
			if(y>Mx)ans+=1LL*(y-Mx)*la,y=Mx;
			if(x>Mx)ans-=1LL*(x-Mx)*la,x=Mx;
			ans+=pre[y]-pre[x];
		}
		printf("Case #%d: %lld\n",T,ans);
	}
	return 0;
}