15.10.05【单调队列、混合背包、强连通+最短路】

OI&ACM, OI训练
  1. 1.发射站(station)
  2. 2.物品选取（pack）
  3. 3.正则表达式（regexp）

100+100+35

1.发射站(station)

【问题描述】 某地有N个能量发射站排成一行，每个发射站i都有不相同的高度Hi，并能向两边（当然两端的只能一边）同时发射能量值为Vi的能量，并且发出的能量只被两边最近的且比它高的发射站接收。 显然，每个发射站发来的能量有可能被0或1或2个其他发射站所接受，特别是为了安全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计算出接收最多能量的发射站接收的能量是多少。

爆搜的话70分 单调队列OK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstring>
#include<cstdio>
using namespace std;
int n,ans,r,h[1000001],v[1000001],sum[1000001];
struct node{
	int x,num;
}f[1000001];
int main()
{
	freopen("station.in","r",stdin);
	freopen("station.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%d%d",&h[i],&v[i]);
	for(int i=1;i<=n;i++)
	{
		while(r>0&&f[r].x<h[i])
		{
			sum[i]+=v[f[r].num];
			f[r].x=f[r].num=0;
			r--;
		}
		f[++r].x=h[i];f[r].num=i;
	}
	memset(f,0,sizeof(f));r=0;
	for(int i=n;i>=1;i--)
	{
		while(r>0&&f[r].x<h[i])
		{
			sum[i]+=v[f[r].num];
			f[r].x=f[r].num=0;
			r--;
		}
		f[++r].x=h[i];f[r].num=i;
	}
	for(int i=1;i<=n;i++)
	  if(sum[i]>ans) ans=sum[i];
	printf("%d",ans);
}

2.物品选取（pack）

【问题描述】 小X可以选择的物品有n样，一共分为甲乙丙三类： 1．甲类物品的价值随着你分配给他的背包体积变化，它的价值与分配给它的体积满足函数关系式，v(x) = A*x^2-Bx，A，B是每个甲类物品的两个参数。注意每个体积的甲类物品只有一个。 2．乙类物品的价值A和体积B都是固定的，但是每个乙类物品都有个参数C，表示这个物品可供选择的个数。 3．丙类物品的价值A和体积B也是固定的，但是每个丙类物品可供选择的个数都是无限多个。 你最终的任务是确定小X的背包最多能装有多大的价值上路。

混合背包（一定要把所有的背包背熟呀！！！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
using namespace std;
int n,m,x,y,A,B,C;
int f[2010];
int main()
{
	freopen("pack.in","r",stdin);
	freopen("pack.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&A,&B);
		if(x==1)
		{
			for(int v=B/A+1;v<=m;v++)
			  for(int j=m;j>=v;j--)
			  {
				y=f[j-v]+A*v*v-B*v;
				if(y>f[j]) f[j]=y;
			  }
		}
		else if(x==2)
		{
			scanf("%d",&C);
			for(int k=1;k<=C;k++)
			  for(int j=m;j>=k*B;j--)
			  {
			  	y=f[j-B]+A;
			  	if(y>f[j]) f[j]=y;
			  }
		}
		else if(x==3)
		{
			for(int j=B;j<=m;j++)
			{
				y=f[j-B]+A;
				if(y>f[j]) f[j]=y;
			}
		}
	}
	printf("%d",f[m]);
}

3.正则表达式（regexp）

【问题描述】 在Internet网络中的每台电脑并不是直接一对一连通的，而是某些电脑之间存在单向的网络连接，也就是说存在A到B的连接不一定存在B到A的连接，并且有些连接传输速度很快，有些则很慢，所以不同连接传输所花的时间是有大有小的。另外，如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。 现在小Z告诉你整个网络的构成情况，他希望知道从他的电脑（编号为1），到小X的电脑（编号为n）所需要的最短传输时间。

本来想找到所有的环，不会写dfs，写了n个SPFA。。。结果35 正解 强连通分量 Tarjan算法 然而数据太大，有30分爆栈了 ~~~ (>_<) ~~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=200010,M=1000010;
queue<int> q;
vector<int> to[N],cost[N];
int n,m,x,y,inf,tot,time,top;
int dfn[N],low[N],stack[N],fa[N],ds[N],u[M],v[M],w[M];
bool vis[N];
void Tarjan(int i)
{
	int j;
	dfn[i]=low[i]=++time;
	vis[i]=1;
	stack[++top]=i;
	for(int e=0;e<to[i].size();e++)
	{
		j=to[i][e];
		if(!dfn[j])
		{
			Tarjan(j);
			if(low[j]<low[i]) low[i]=low[j];
		}
		else if(vis[j]&&dfn[j]<low[i]) low[i]=dfn[j];	
	}
	if(dfn[i]==low[i])
	{
		do
		{
		    j=stack[top--];
		    fa[j]=fa[i];
			vis[j]=0;
		}while(j!=i);
	}
}
int main()
{
	freopen("regexp.in","r",stdin);
	freopen("regexp.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&w[i]);
		u[i]=x;v[i]=y;
		to[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	  if(!dfn[i]) Tarjan(i);
	memset(to,0,sizeof(to));
	for(int i=1;i<=m;i++)
	{
		x=fa[u[i]];y=fa[v[i]];
		if(x!=y)  to[x].push_back(y),cost[x].push_back(w[i]);
	}
	memset(ds,0x7f,sizeof(ds));
	memset(vis,0,sizeof(vis));
	ds[1]=0; vis[1]=1; q.push(1);
	while(!q.empty())
	{
		int x=q.front(); q.pop(); vis[x]=0;
		for(int i=0;i<to[x].size();i++)
		{
			int y=to[x][i],c=cost[x][i];
			if(ds[y]>ds[x]+c)
			{
				ds[y]=ds[x]+c;
				if(!vis[y])
				{
					vis[y]=1; q.push(y);
				}
			}
		}
	}
	printf("%d",ds[n]);
}