Yurchiu's Blog
Yurchiu
An AFO whker.
  首页
  归档
158
  标签
81
  分类
24
  说说
  关于
  留言
  链接
  设置

P1850 [NOIP2016 提高组] 换教室

xzy,fsl,mzf,Yurchiu 2021-08-27, 20:57:50 3.1k 隐藏左右两栏 展示左右两栏
首页 / P1850 [NOIP2016 提高组] 换教室

题意

  • 有 2n2n 节课程安排在 nn 个时间段上。在第 ii（1≤i≤n1 \leq i \leq n）个时间段上，两节内容相同的课程同时在不同的地点进行。

  • Yurchiu 预先被安排在教室 cic_i 上课，而另一节课程在教室 did_i 进行。

  • Yurchiu 需要按时间段的顺序依次完成所有的 nn 节课程。如果想更换第 ii 节课程的教室，则需要提出申请。若申请通过，Yurchiu 就可以在第 ii 个时间段去教室 did_i 上课，否则仍然在教室 cic_i​​ 上课。

  • 申请被通过的概率是一个已知的实数 kik_i​​，并且对于不同课程的申请，通过概率互相独立。

  • 大学有 vv 个教室，有 ee 条道路。每条道路连接两间教室且双向通行。道路有权值，当第 ii（1≤i≤n−11 \leq i \leq n-1​）节课结束后，从此教室出发，选择一条权值最小的路径前往下一节课的教室。

Yurchiu 想知道申请哪几门课程可以使她因在教室间移动而产生的权值和的期望值最小。只需求出这个最小值。

点击查看题解

题解

本题解来自 3 位大佬的课件。

0x01 24 pts

m=0m=0​​ 就意味着无法申请，这就和期望无关了。于是，只要求出各个点之间的最短路，按时间加起来就可以了。

使用 floyd 算法求最短路计算任意两个教室之间的最短路。

注意：

  1. for 循环的范围是 1∼v1\sim v，而不是 1∼n1\sim n。
  2. 不要忘记 i=ji=j​ 时，disi,j=0dis_{i,j}=0​ （1212​​​ 分，我不知道为什么会得分）。非常重要，对于其他题目也适用。
  3. floyd 算法使用邻接矩阵存储图，注意重边的处理。

时间复杂度 O(v3+n)O(v^3+n)​。

void _24pts()
{
	for(ll i=2;i<=n;i++)
	{
		ans+=dis[c[i-1]][c[i]];
		pre[i]=ans;
	}
	return;
}

0x02 52 pts

m=1m=1 时仅能申请一个。图是不变的，仍然跑 floyd。

分为两种情况：

  1. 不申请。相当于 m=0m=0​，与 24 分算法结合。
  2. 申请，又分为两种情况：
    1. 申请成功。需要更改从上一个教室到更换后教室的距离以及更换后教室到下一个教室的距离。按时间段累加距离，并乘 kik_i。
    2. 申请失败。距离不变，乘 (1−ki)(1-k_i)​。

注：

  1. 可以在累加过程中乘概率。
  2. 如果在累加过程中大于已知的 ans，就可以 break。

如此，floyd 后，先算 m=0m=0​ 的情况，后枚举要换的教室，每一次枚举都累加一次。

时间复杂度是 O(v3+n2)O(v^3+n^2)​​​。

void _52pts()
{
	memset(a52,0,sizeof(a52));
	for(ll i=2;i<=n;i++)
		for(ll j=1;j<=n;j++)
		{
			a52[i][j]+=a52[i-1][j];
			if(i==j)
			{
				a52[i][j]+=(dis[c[i-1]][d[i]])*k[i];
				a52[i][j]+=(dis[c[i-1]][c[i]])*(1-k[i]);
			}
			else if(i-1==j)
			{
				a52[i][j]+=(dis[d[i-1]][c[i]])*k[i-1];
				a52[i][j]+=(dis[c[i-1]][c[i]])*(1-k[i-1]);
			}
			else a52[i][j]+=dis[c[i-1]][c[i]];
		}
	for(ll i=1;i<=n;i++)
		ans=min(ans,a52[n][i]);
}

本程序有优化的余地。

  1. a52 数组可以滚动优化，滚掉 1 维（很显然是不是）。
  2. 进一步优化：我们发现，不需要每次从 1 到 n 都累加一遍。只需要在特殊的地方加一下，然后其他的地方前缀和优化即可。

时间复杂度降为 O(v3+n)O(v^3+n)​​。

ll query(ll l,ll r) {return pre[r]-pre[l-1];}
void _52pts()
{
	for(ll i=1;i<=n;i++)
	{
		a52=0;
			
		if(i-1>=1) a52+=(dis[c[i-1]][d[i]])*(k[i]);
		if(i-1>=1) a52+=(dis[c[i-1]][c[i]])*(1-k[i]);
		if(i+1<=n) a52+=(dis[d[i]][c[i+1]])*(k[i]);
		if(i+1<=n) a52+=(dis[c[i]][c[i+1]])*(1-k[i]);
			
		if(i-1>=2) a52+=query(2,i-1);
		if(i+2<=n) a52+=query(i+2,n);
			
		ans=min(ans,a52);
	}
}

0x03 76 pts

m=2m=2 时，分为 3 种情况：

  1. 不申请。
  2. 仅申请一个。
  3. 申请两个。

关于 1 和 2，其实就是 m=1m=1，结合之前的程序即可；关于 3，我们需要枚举申请的是哪两个。

两层循环找组合，复杂度是 O(n2)O(n^2)​。每种组合都累加一下。有 4 种情况：

  1. 都申请成功。
  2. 第一个申请成功，第二个没申请成功。
  3. 第一个没申请成功，第二个申请成功。
  4. 都没申请成功。

类似地，按照 52 分解的处理方法，76 分拿到了。

时间复杂度为 O(v3+n2)O(v^3+n^2)​​。

void _76pts()
{
	for(ll i=1;i<=n-1;i++)
	{
		for(ll j=i+1;j<=n;j++)
		{
			a76=0;
				
			if(i-1>=1) a76+=(dis[c[i-1]][d[i]])*(k[i]);
			if(i-1>=1) a76+=(dis[c[i-1]][c[i]])*(1-k[i]);
			if(j+1<=n) a76+=(dis[d[j]][c[j+1]])*(k[j]);
			if(j+1<=n) a76+=(dis[c[j]][c[j+1]])*(1-k[j]);
				
			if(i+1==j)
			{
				a76+=(dis[d[i]][d[j]])*(k[i]*k[j]);
				a76+=(dis[d[i]][c[j]])*(k[i]*(1-k[j]));
				a76+=(dis[c[i]][d[j]])*((1-k[i])*k[j]);
				a76+=(dis[c[i]][c[j]])*((1-k[i])*(1-k[j]));
			}
			else
			{
				a76+=(dis[d[i]][c[i+1]])*(k[i]);
				a76+=(dis[c[i]][c[i+1]])*(1-k[i]);
				a76+=(dis[c[j-1]][d[j]])*(k[j]);
				a76+=(dis[c[j-1]][c[j]])*(1-k[j]);
			}
				
			if(i-1>=2) a76+=query(2,i-1);
			if(j+2<=n) a76+=query(j+2,n);
			if(i+2<=j-1) a76+=query(i+2,j-1);
				
			ans=min(a76,ans);
		}
	}
}

0x04 100 pts

考虑使用动态规划来解。

显然，nn 和 mm 是 dp 过程中不可忽略的状态。接下来对此探究一下：

在之前的骗分过程中，我们很容易发现申请不同的个数是互不影响的，那我们仅考虑申请已知个数时如何进行选择。这就与申请个数的分配有关了。

初始的想法是用区间 dp 的思想去设计状态：设 f[i][j][k] 表示时间段 [i,j][i,j] 分配了 kk 个申请的最优解。发现这样需要 4 层循环（枚举 ii，jj，kk 和 midmid），显然，时间复杂度过高。

这样，我们可以舍弃左端点。

设 f[i][j] 表示时间段 [1,i] 分配了 jj 个申请的最优解。这样枚举 ii 和 jj，看 f[i][j] 可以由哪些状态转移来。时间复杂度可以接受。

我们要做到从 i−1i-1​​ 到 ii​​​，在推进过程中一步步取最优。这就需要我们知道新增时间段是否申请：

  1. 若 ii 不申请，那么就看 i−1i-1 申不申请。
  2. 若 ii 申请，同样要看 i−1i-1 申不申请。

无疑，我们需要知道时间段 i−1i-1​​​ 的教室有没有换。即下一个状态 f[i][j] 的转移和 i−1i-1​​ 是否申请成功有关。于是，我们再加一维 0/1，表示 ii​​​ 是否申请成功。

看来，我们既需要知道 ii​​ 是否申请，也要知道 i−1i-1​​ 是否申请。于是，我们可以设 add[0/1][0/1] 表示当我们考虑到 ii​ 时，i−1i-1​​ 和 ii​​ 是否申请而造成的新的代价。

状态转移方程很冗杂，但很好推。可以结合代码进行理解。

void _100pts()
{
	for(ll i=0;i<=n;i++)
		for(ll j=0;j<=m;j++)
			f[i][j][0]=f[i][j][1]=inf;
	f[1][0][0]=f[1][1][1]=0;//刚开始的教室，无论换还是不换，都相当于不用跑路 
	for(ll i=2;i<=n;i++)
	{
		add[0][0]=dis[c[i-1]][c[i]];
		add[0][1]=dis[c[i-1]][c[i]]*(1-k[i])+
				  dis[c[i-1]][d[i]]*(k[i]);
		add[1][0]=dis[c[i-1]][c[i]]*(1-k[i-1])+
				  dis[d[i-1]][c[i]]*(k[i-1]);
		add[1][1]=dis[c[i-1]][c[i]]*((1-k[i-1])*(1-k[i]))+
				  dis[c[i-1]][d[i]]*((1-k[i-1])*k[i])+
				  dis[d[i-1]][c[i]]*(k[i-1]*(1-k[i]))+
				  dis[d[i-1]][d[i]]*(k[i-1]*k[i]);
			
		f[i][0][0]=f[i-1][0][0]+add[0][0];
		for(ll j=1;j<=min(m,i);j++)
		{
			f[i][j][0]=min(f[i][j][0],
					   min(f[i-1][j][0]+add[0][0],
						   f[i-1][j][1]+add[1][0]));
							   
			f[i][j][1]=min(f[i][j][1],
					   min(f[i-1][j-1][0]+add[0][1],
						   f[i-1][j-1][1]+add[1][1]));
		}
	}
	for(ll i=0;i<=m;i++)
	{
		ans=min(ans,f[n][i][0]);
		ans=min(ans,f[n][i][1]);
	}
}

代码

这里是所有部分分解和正解的代码。如果单独跑 _100pts() 需要把 ans 置为 inf，而且更快。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll V=300+10,N=2000+10,inf=2147483647;
	ll dis[V][V],n,m,v,e,c[N],d[N],pre[N];
	double k[N],ans=0,a52,a76,a100,add[2][2];
	double f[N][N][2];
	void _24pts()
	{
		for(ll i=2;i<=n;i++)
		{
			ans+=dis[c[i-1]][c[i]];
			pre[i]=ans;
		}
		return;
	}
	ll query(ll l,ll r) {return pre[r]-pre[l-1];}
	void _52pts()
	{
		for(ll i=1;i<=n;i++)
		{
			a52=0;
			
			if(i-1>=1) a52+=(dis[c[i-1]][d[i]])*(k[i]);
			if(i-1>=1) a52+=(dis[c[i-1]][c[i]])*(1-k[i]);
			if(i+1<=n) a52+=(dis[d[i]][c[i+1]])*(k[i]);
			if(i+1<=n) a52+=(dis[c[i]][c[i+1]])*(1-k[i]);
			
			if(i-1>=2) a52+=query(2,i-1);
			if(i+2<=n) a52+=query(i+2,n);
			
			ans=min(ans,a52);
		}
	}
	void _76pts()
	{
		for(ll i=1;i<=n-1;i++)
		{
			for(ll j=i+1;j<=n;j++)
			{
				a76=0;
				
				if(i-1>=1) a76+=(dis[c[i-1]][d[i]])*(k[i]);
				if(i-1>=1) a76+=(dis[c[i-1]][c[i]])*(1-k[i]);
				if(j+1<=n) a76+=(dis[d[j]][c[j+1]])*(k[j]);
				if(j+1<=n) a76+=(dis[c[j]][c[j+1]])*(1-k[j]);
				
				if(i+1==j)
				{
					a76+=(dis[d[i]][d[j]])*(k[i]*k[j]);
					a76+=(dis[d[i]][c[j]])*(k[i]*(1-k[j]));
					a76+=(dis[c[i]][d[j]])*((1-k[i])*k[j]);
					a76+=(dis[c[i]][c[j]])*((1-k[i])*(1-k[j]));
				}
				else
				{
					a76+=(dis[d[i]][c[i+1]])*(k[i]);
					a76+=(dis[c[i]][c[i+1]])*(1-k[i]);
					a76+=(dis[c[j-1]][d[j]])*(k[j]);
					a76+=(dis[c[j-1]][c[j]])*(1-k[j]);
				}
				
				if(i-1>=2) a76+=query(2,i-1);
				if(j+2<=n) a76+=query(j+2,n);
				if(i+2<=j-1) a76+=query(i+2,j-1);
				
				ans=min(a76,ans);
			}
		}
	}
	void _100pts()
	{
		for(ll i=0;i<=n;i++)
			for(ll j=0;j<=m;j++)
				f[i][j][0]=f[i][j][1]=inf;
		f[1][0][0]=f[1][1][1]=0;//刚开始的教室，无论换还是不换，都相当于不用跑路 
		for(ll i=2;i<=n;i++)
		{
			add[0][0]=dis[c[i-1]][c[i]];
			add[0][1]=dis[c[i-1]][c[i]]*(1-k[i])+
					  dis[c[i-1]][d[i]]*(k[i]);
			add[1][0]=dis[c[i-1]][c[i]]*(1-k[i-1])+
					  dis[d[i-1]][c[i]]*(k[i-1]);
			add[1][1]=dis[c[i-1]][c[i]]*((1-k[i-1])*(1-k[i]))+
					  dis[c[i-1]][d[i]]*((1-k[i-1])*k[i])+
					  dis[d[i-1]][c[i]]*(k[i-1]*(1-k[i]))+
					  dis[d[i-1]][d[i]]*(k[i-1]*k[i]);
			
			f[i][0][0]=f[i-1][0][0]+add[0][0];
			for(ll j=1;j<=min(m,i);j++)
			{
				f[i][j][0]=min(f[i][j][0],
						   min(f[i-1][j][0]+add[0][0],
							   f[i-1][j][1]+add[1][0]));
							   
				f[i][j][1]=min(f[i][j][1],
						   min(f[i-1][j-1][0]+add[0][1],
							   f[i-1][j-1][1]+add[1][1]));
			}
		}
		for(ll i=0;i<=m;i++)
		{
			ans=min(ans,f[n][i][0]);
			ans=min(ans,f[n][i][1]);
		}
	}
	void yzmain()
	{
		ll t1,t2,t3;
		scanf("%lld%lld%lld%lld",&n,&m,&v,&e);
		for(ll i=1;i<=n;i++) scanf("%lld",c+i);
		for(ll i=1;i<=n;i++) scanf("%lld",d+i);
		for(ll i=1;i<=n;i++) scanf("%lf",k+i);
		for(ll i=1;i<=v;i++)
			for(ll j=1;j<=v;j++)
				if(i!=j) dis[i][j]=inf;
		for(ll i=1;i<=e;i++)
		{
			scanf("%lld%lld%lld",&t1,&t2,&t3);
			dis[t1][t2]=dis[t2][t1]=min(dis[t1][t2],t3);
		}
		for(ll k=1;k<=v;k++)
			for(ll i=1;i<=v;i++)
				for(ll j=1;j<=v;j++)
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		_24pts();
		if(m>=1) _52pts();
		if(m>=2) _76pts();
		if(m>=3) _100pts();
		printf("%.2lf\n",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}



本文作者：xzy,fsl,mzf,Yurchiu

本文链接：https://yz-hs.github.io/b50c00ca3042/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。


OI 图论 动态规划 最短路 数学期望
最后更新：2023-08-21, 23:18:20
By Yurchiu.
最近更新旧文更新
[Works] 自白 终章
《幽默报 10》
AFO 有感
OI 之旅
《幽默报》
[Works] 自白
[Idea] 试卷排序
其他物件杂物收纳
Hitokoto

Yurchiu 说，除了她以外的人都很强！嘤嘤嘤~~
博客信息
文章数目
158
最近更新
08-21
本站字数
350.6k
文章目录

©2019-2023 Yurchiu. All rights reserved.

Theme Cutie, by Yurchiu.