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

  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]);
}