CF1874G Jellyfish and Inscryption 做题记录

给定一张 $n$ 个点 $m$ 条边的 DAG，每条边 $u_i\to v_i$ 都满足 $u_i<v_i$ 。

点有五种类型：

无特殊事件；

走到这里会获得一个二元组 $(a,b)$ ；

走到这里可以选择一个之前获得的二元组，将其的 $a$ 增加 $x$ ；

走到这里可以选择一个之前获得的二元组，将其的 $b$ 增加 $x$ ；

走到这里会获得一个数 $w$ ；

你要从点 $1$ 走到点 $n$ ，保证点 $1$ 和点 $n$ 是 $1$ 类点。

走到点 $n$ 时可以选择一个之前获得的二元组，将其的 $b$ 乘上 $10^9$ 。

最大化最终获得的所有二元组的 $a\times b$ 的和加上获得的数 $w$ 的和。

$1\le n\le 200$ ， $1\le m\le \min(\frac{n(n-1)}{2},2000)$ ， $1\le a,b,x\le 200$ ， $1\le w\le 10^6$ 。

下文设 $V=200$ 。

这个最后乘 $10^9$ 的操作其实相当于先最大化 $a\times b$ 的最大值，再最大化 $\sum a\times b$ 。

考虑枚举这个最大的 $(a,b)$ 是点 $u$ 处加入的，那么 $u\to n$ 路径上的 $(+x,0)$ 和 $(0,+x)$ 一定都操作到它的头上。这部分的贡献可以简单 dp 算出：

设 $f_{u,a}=(b,w)$ 表示从 $u$ 出发走到 $n$ 且 $(+x,0)$ 操作的和为 $(+a,0)$ 时， $(0,+x)$ 操作的和最大为 $(0,+b)$ ，在此前提下其余贡献（ $+w$ 和其它二元组的 $+a\times b$ ）最大为 $w$ ；

现在问题在于计算 $1\to u$ 的最大贡献。

不难发现，点 $u$ 的二元组 $(a_u,b_u)$ 若在点 $v$ 处被操作了 $(+x_v,0)$ ，那么 $u\to v$ 路径上的所有 $(+x_v,0)$ 都应该操作到 $u$ 头上。所以一个二元组一旦不再成为 $(+x,0)$ 的目标，那么它之后就再也不会成为 $(+x,0)$ 的目标了。 $(0,+x)$ 同理。

所以现在有一个 $O(n^3V^2)$ 的 dp：

设 $f_{u,a,b,0/1}$ 表示从 $1$ 走到了 $u$ ，当前 $(0,+x)$ 操作的目标二元组是 $(a,*)$ ，当前 $(+x,0)$ 操作的目标二元组是 $(*,b)$ ，这两个二元组是否来自同一个点（是否是二元组 $(a,b)$ ）；

转移只需要考虑新加入的二元组是否会干掉 $(a,*)$ 和 $(*,b)$ 或者两个都干掉。

进一步，如果 $a>V$ 且 $b>V$ ，那么该状态一定是 $f_{u,a,b,1}$ ，即对应二元组为 $(a,b)$ 。那么 $u\to n$ 路径上的 $(+x,0)$ 和 $(0,+x)$ 一定都会操作到它头上，所以这个二元组可以看作是最后 $a\times b$ 最大的那个，即我们在钦定 $(a_u,b_u)$ 作为 $a\times b$ 最大的那个二元组计算答案时已经算过这种情况。

所以有 $\min(a,b)\le V$ ，而注意到 $a$ 和 $b$ 在转移过程中不会减少，所以可以把一维开到 $V$ 。不妨假定 $a\le V$ ，这样交换 $a,b$ 再做一次即可。

那么这个 dp 被优化到了 $O(n^2V^2)$ 。

继续。考虑二元组的贡献形如 $(a+\sum x)\times (b+\sum x)$ ，我们这个 dp 算贡献的方式是加入一个元素就算一次它和当前另一边的贡献，所以两边的总和都要记录。

注意到根据之前的性质，有 $a+\sum x\le V$ ，那么不妨直接钦定左边 $a+\sum x$ 的值，将算贡献的方式改为每次加入一个右边的元素 $z$ （ $b$ 或 $(0,+x)$ ）时贡献 $(a+\sum x)\times z$ ，相当于将 $(+x,0)$ 操作“预支”出去。再根据一个二元组 $(a,b)$ 一定是在路径的一个区间内成为 $(+x,0)$ 操作的目标，故每个时刻只有最多一个二元组的债还未偿还。

那么有 dp：

设 $f_{u,a,k}$ 表示从 $1$ 走到了 $u$ ，当前 $(a+\sum x)$ 为 $a$ ，还欠了 $k$ 的债；

转移是简单的，时间复杂度 $O((n+m)V^2)$ 。

注意要特判没有 $1$ 类点的情况，代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

const int S=205,MUL=1000000000;
const ll inf=1e17;

int n,m;
int tp[S],a[S],b[S];
vector<int> g[S],rg[S];
ll f[S][S][S],res[S];
pair<ll,ll> h[S][S*S];

template<typename T>
inline void tmax(T &x,T y){x=max(x,y);}

inline void doit()
{
	for(int i=1;i<=n;i++)
		for(int j=0;j<=S-3;j++)
			for(int k=0;k<=S-3;k++) f[i][j][k]=-inf;
	f[1][0][0]=0;
	for(int i=1;i<=n;i++)
		for(int v:g[i])
			for(int j=0;j<=S-3;j++)
				for(int k=0;k<=S-3;k++)
				{
					ll u=f[i][j][k];
					if(u<0) continue;
					if(tp[v]==0) tmax(f[v][j][k],u);
					if(tp[v]==1)
					{
						tmax(f[v][max(j,a[v])][k],u+a[v]*b[v]);
						if(k==0)
						{
							for(int x=a[v];x<=S-3;x++)
								tmax(f[v][max(j,x)][x-a[v]],u+x*b[v]);
						}
					}
					if(tp[v]==2) tmax(f[v][j][max(0,k-a[v])],u);
					if(tp[v]==3) tmax(f[v][j][k],u+j*b[v]);
					if(tp[v]==4) tmax(f[v][j][k],u+a[v]);
				}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=S-3;j++) tmax(res[i],f[i][j][0]);
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>tp[i];
		if(tp[i]==0) continue;
		if(tp[i]==1) cin>>a[i]>>b[i];
		if(tp[i]==2) cin>>a[i];
		if(tp[i]==3) cin>>b[i];
		if(tp[i]==4) cin>>a[i],b[i]=a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		rg[y].push_back(x);
	}
	for(int i=1;i<=n;i++) res[i]=-inf;
	doit();
	for(int i=1;i<=n;i++)
	{
		swap(a[i],b[i]);
		if(tp[i]==2||tp[i]==3) tp[i]=2+3-tp[i];
	}
	doit();
	for(int i=1;i<=n;i++)
		for(int j=0;j<=S*S-3;j++) h[i][j]=make_pair(-inf,-inf);
	h[n][0]=make_pair(0,0);
	for(int i=n;i>=1;i--)
		for(int v:rg[i])
			for(int j=0;j<=S*S-3;j++)
			{
				pair<ll,ll> u=h[i][j];
				if(u.first<0) continue;
				if(tp[v]==0) tmax(h[v][j],u);
				if(tp[v]==1)
					tmax(h[v][j],make_pair(u.first,u.second+a[v]*b[v]));
				if(tp[v]==2&&j+a[v]<=S*S-3)
					tmax(h[v][j+a[v]],u);
				if(tp[v]==3)
					tmax(h[v][j],make_pair(u.first+b[v],u.second));
				if(tp[v]==4)
					tmax(h[v][j],make_pair(u.first,u.second+a[v]));
			}
	ll ans=0;
	for(int i=1;i<=n;i++)
		if(tp[i]==1)
			for(int j=0;j<=S*S-3;j++)
			{
				if(h[i][j].first<0) continue;
				ll pre=res[i]+h[i][j].second-a[i]*b[i]*2;
				ll val=(a[i]+j)*(b[i]+h[i][j].first);
				tmax(ans,pre+val*MUL);
			}
	for(int i=0;i<=S-3;i++) tmax(ans,f[n][i][0]);
	cout<<ans<<'\n';
	return 0;
}
/*
给一条路径怎么做
每次是选择另一边最大的那个加上吗？好像不是 fake
不过我还是可以记录两个点表示 +a 操作和 +b 操作的目标点 x,y
一个点退出目标点后就不可能重新变成目标点
新的目标点只可能是新加入的点或者 x,y
如果一个点变成了海王，那么不如让它存活区间的所有增加操作都操作到他头上
那么我怎么维护这种情况
相当于求出 x 到 y 路径上，所有增加操作都操作到 x 头上的最大值
鉴于我最后那个 *1e9 的操作，首先要最大化乘积最大的

5 1
4 6

+1e9   0
  0  +1e9
  
I am pig

	* 目标点的值不可能同时大于 V，这是因为大于 V 必定两点重合，
		不如把 1e9 放到这里

默认 a 没有大于 V，设 f[i][x][y][0/1] 表示在点 i，
	(a,b) 目标点的值分别为 x 和 y，两个目标点是否重合
转移考虑只有可能是新加入的点替换掉某一个目标点
n^2V^2

提前算贡献，默认 a 没有大于 V，设 f[i][x][y] 表示在点 i，
	a 目标点最终是 x，这个目标点欠了 y 的债务
	只有还掉了上一个目标点的债务才能更新目标点
*/

CF1874G Jellyfish and Inscryption 做题记录

感谢您的支持，我会继续努力的!