[ 牛客网暑期ACM多校训练营(第二场) ] B Discount

Zarxdy34 posted @ 2018年7月21日 23:11 in Nowcoder with tags DP 基环外向树 , 556 阅读

        题目大意:有n个物品,第i个物品的价格为\(p_i\),对每个物品,有两种优惠策略,可以选择其一:

        1.购买该物品可以得到\(d_i\)元的打折(即购买该物品只需\(p_i - d_i\)元)。

        2.购买该物品后可以免费购买第\(f_i\)个物品。

        求购买n个物品的最小花费。其中\(1 \leq n \leq 10^5 , 0 \leq d_i \leq p_i \leq 10^9 , 1 \leq f_i \leq n\)。

 

        题解:将每个物品i与物品\(f_i\)连边,可以得到一个基环外向树,然后我们要做的事情就是在这上面做DP。把环拿出来,剩下的就是一堆树,分原价购买以及(免费或打折购得)两种状态进行DP,在环上DP时再记录DP的第一个物品的状态。

 

#include <bits/stdc++.h>
using namespace std;
const long long inf=~0ull>>2;
const int maxn=1e5+10;

int head[maxn],nxt[maxn<<1],E[maxn<<1],Ecnt;
int DFN[maxn],Low[maxn],ID[maxn],GQ[maxn],cnt,GQN,Index;
long long F[maxn][2],G[maxn][3][2];
int p[maxn];
int d[maxn];
int f[maxn];
int n;
long long ans;

void Add_Edge(int x,int y)
{
	nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;
	nxt[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;
}

int Q[maxn],Inq[maxn],qtop;
void Tarjan(int x)
{
	DFN[x]=Low[x]=++Index;
	Q[++qtop]=x;
	Inq[x]=1;
	if (!DFN[f[x]]) Tarjan(f[x]),Low[x]=min(Low[x],Low[f[x]]);
	else if (Inq[f[x]]) Low[x]=min(Low[x],DFN[f[x]]);
	if (DFN[x]==Low[x])
	{
		cnt++;
		while (Inq[x])
		{
			int u=Q[qtop--];
			Inq[u]=0;
			ID[u]=cnt;
		}
	}
}

void DFS(int x)
{
	ID[x]=-1;
	GQ[++GQN]=x;
	for (int i=head[x];i;i=nxt[i]) if (!ID[E[i]]) DFS(E[i]);
}

void Solve_Subtree(int x)
{
	for (int i=head[x];i;i=nxt[i]) if (ID[E[i]]!=ID[x] && f[x]!=E[i]) Solve_Subtree(E[i]);
	long long fmin=0,fmin_one=0;
	for (int i=head[x];i;i=nxt[i]) if (ID[E[i]]!=ID[x] && f[x]!=E[i])
	{
		if (F[E[i]][1]<=F[E[i]][0]) fmin_one=1,fmin+=F[E[i]][1];
		else fmin+=F[E[i]][0];
	}
	F[x][1]=fmin+p[x];
	if (fmin_one) F[x][0]=fmin;
	else {
		F[x][0]=inf;
		for (int i=head[x];i;i=nxt[i]) if (ID[E[i]]!=ID[x] && f[x]!=E[i])
			F[x][0]=min(F[x][0],fmin-F[E[i]][0]+F[E[i]][1]);
	}
	F[x][0]=min(F[x][0],fmin+p[x]-d[x]);
}

long long Solve_Circle(int x)
{
	if (f[x]==x) return min(F[x][0],F[x][1]);
	int last=x,sx=x;
	G[x][0][0]=F[x][1]-p[x];
	G[x][0][1]=inf;
	G[x][1][0]=F[x][0];
	G[x][1][1]=inf;
	G[x][2][1]=F[x][1];
	G[x][2][0]=inf;
	for (x=f[x];x!=sx;last=x,x=f[x])
	{
		for (int j=0;j<3;j++)
		{
			G[x][j][0]=min(G[last][j][1]+F[x][1]-p[x],min(G[last][j][0],G[last][j][1])+F[x][0]);
			G[x][j][1]=min(G[last][j][0],G[last][j][1])+F[x][1];
		}
		if (f[x]==sx)
		{
			long long res=inf;
			res=min(G[last][0][0],G[last][0][1])+F[x][1];
			res=min(res,G[x][1][0]);
			res=min(res,G[x][1][1]);
			res=min(res,G[x][2][0]);
			res=min(res,G[x][2][1]);
			return res;
		}
	}
	return 0;
}

long long Solve()
{
	if (GQN==1) return p[GQ[1]]-d[GQ[1]];
	int Cir_ID=0;
	for (int i=1;i<=GQN;i++) if (ID[GQ[i]]==ID[f[GQ[i]]]) Cir_ID=ID[GQ[i]];
	for (int i=1;i<=GQN;i++) if (ID[GQ[i]]==Cir_ID) Solve_Subtree(GQ[i]);
	for (int i=1;i<=GQN;i++) if (ID[GQ[i]]==Cir_ID)
		return Solve_Circle(GQ[i]);
	return 0;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&p[i]);
	for (int i=1;i<=n;i++) scanf("%d",&d[i]);
	for (int i=1;i<=n;i++) scanf("%d",&f[i]),Add_Edge(i,f[i]);
	for (int i=1;i<=n;i++) if (!DFN[i])
	{
		cnt=GQN=Index=0;
		DFS(i);
		for (int j=1;j<=GQN;j++) if (!DFN[GQ[j]]) Tarjan(GQ[j]);
		ans+=Solve();
	}
	printf("%lld\n",ans);
	return 0;
}

 

Avatar_small
boardmodelpaper.com 说:
2024年1月19日 12:42

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter