CF1455G Forbidden Value

本题教训我们：

如果遇到在返回值域范围的dp时，可以考虑线段树合并操作。

考虑最开始写作一个\(if:0;end\)

那么所有的\(if\)可以记作一个树状结构，\(set\)为子节点

先把所有\(set\ s\)指令删除，代价提前至点上。

考虑在树上\(dp\)，那么我们需要的是\(f_{i,j}\)即操作完 \(i\) 内的子程序后，返回值为 \(j\) 的最小代价。

那么可以线段树合并操作。

但是由于这个子节点之间的顺序有差别，所以这里可以采用顺序访问子节点而后map启发式合并。

复杂度较线段树合并为\(O(nlog^2n)\)多一个\(log\)。

下午再来补上程序。

机房的dev居然没法C++14.

#include<bits/stdc++.h>

#define N 200020

#define ll long long

int n,ban,x[N],w[N],f[N];

ll d[N];

std::string opt[N];

std::vector<int>G[N];//树

std::map<int,ll>dp[N];//启发式合并map

std::multiset<ll>num[N];//处理最小值 

inline void dfs(int u){

	dp[u][x[u]] = 0;

	num[u].insert(0);

	for(int i = 0;i < G[u].size();++i){

		int v = G[u][i];

		if(opt[v][0] == 's'){

			if(x[v] == ban)

			d[u] += w[v];

			else

			if(dp[u].count(x[v])){

				ll las = dp[u][x[v]];

				dp[u][x[v]] = (*num[u].begin()) - w[v];

				num[u].erase(num[u].find(las));

			}else{

				dp[u][x[v]] = (*num[u].begin()) - w[v];

			}

			num[u].insert(dp[u][x[v]]);

			d[u] += w[v];

		}

		else{

		if(dp[u].count(x[v])){//如果可能进入这个if

			dfs(v);

			ll tmp = d[v] + dp[u][x[v]];

			if(dp[v].size() <= dp[u].size()){

				for(auto [k,t] : dp[v]){

				if(!dp[u].count(k))dp[u][k] = tmp + t;

				else{

					num[u].erase(num[u].find(dp[u][k]));

					dp[u][k] = std::min(k == x[v] ? inf : dp[u][k],tmp + t);

				}

				num[u].insert(dp[u][k]);

				}

			}else{

				d[u]+=tmp;

				for(auto [k,t]:dp[u]){

					if(!dp[v].count(k))dp[v][k]=t-tmp;

					else{

						num[v].erase(num[v].find(dp[v][k]));

						if(k^x[v])dp[v][k]=min(dp[v][k],t-tmp);

					}

					num[v].insert(dp[v][k]);

				}

				std::swap(dp[u],dp[v]);

				std::swap(num[u],num[v]);

			}

		}

	}

}

}

int main(){

	scanf("%d%d",&n,&ban);

	int u = 0;

	for(Int i = 1;i <= n;++i){

		std::cin>>opt[i];

		if(opt[i][0] == 's'){

			G[u].push_back(i);

			scanf("%d%d",&x[i],&w[i]);

		}else if(opt[i][0] == 'i'){

			scanf("%d",&x[i]);

			G[u].push_back(i);

			f[i] = u;

			u = i;

		}else{

			u = f[u];

		}

	}

	dfs(0);

	std::cout<<(d[0] + *num[0].begin())<<std::endl;

}

巴特西

CF1455G Forbidden Value

最新文章

热门文章