LOJ2335「JOI 20162017 决赛」足球

题目

LOJ题目链接

吐槽

​ 机房有人在打一场奇怪的比赛(sxd666888AK了这场比赛),当时看了一下最后一题,本来想特判一下n=2的点然后跑,结果发现过了,赶紧交了个0分代码跑路防止阻挡sxd666888神犇的光芒?后来找到了原题就是这道。

题解

​ 做法大抵和网上题解差不多,思路可能有点区别。

​ 首先可以发现一个优秀的性质:最优解的情况下,不存在一个球员把球传出之后再收到。

​ 也就是说,如果我们不管是哪个球员接的,我们假装他是没动过,直接从原来的位置来拿这个球,是不会影响最优解的。

​ 设f[i][j]f[i][j]表示到球在第i行第j列的时候,某一个球员控制着球,最小的代价是多少。

​ 设g[i][j]g[i][j]表示离第i行第j列最近的球员跑到这个位置的代价是多少。

​ 那么可以得到若干个转移方程:

1、从(i,j)到(i+1,j),(i-1,j),(i,j-1),(i,j+1)这四个方向转移,代价为C,表示运球。

2、从(i,j)到(k,j),代价为abs(ik)×A+B+g[k][j]abs(i-k) \times A + B + g[k][j],表示传球到某个位置,让另一个人接收。

3、从(i,j)到(i,k),代价为abs(jk)×A+B+g[i][j]abs(j-k) \times A + B + g[i][j],意义同上。

​ 发现这东西可以用最短路来转移,又显然都是正权边,可以用dijkstradijkstra来转移,最后得到的答案就是f[S[n]][T[n]]f[S[n]][T[n]]

​ 设M=(W+1)×(H+1)M = (W+1) \times (H+1),那么这么做点数是M,边数大约是是4×M+M×(W+H)4 \times M + M \times (W+H)

​ 然后可以发现2、3可以轻松地优化,每列每行新建辅助点,相邻辅助点之间连A,点与赋值点之间连B或者是g[x][y]g[x][y],这样点是3×M3 \times M的,边大约是12×M12 \times M,是能够通过这题的。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//数组我没有具体算,直接开大了好多好多倍(,相信你也看得出来,这大概就是菜的人吧
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll inf = 1ll<<62;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define BASE ((W+1)*(H+1))
#define pc putchar
#define fi first
#define se second
#define debug(x) cout << #x" = " << x << endl;
#define pp(x,y) cout << "pp: " << x << " " << y << endl;
#define gc getchar
#define rank __RANK
inline ll read(){
register ll x=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
#define rd read
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
#define mem(x,v) memset(x,v,sizeof(x))
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define min(x,y) ((x)<(y)?(x):(y))
const int maxn = 1005*1005;
int W,H,n,A,B,C;
struct Edge{
int to,nxt,dist;
Edge(){}
Edge(int to,int nxt,int dist):
to(to),nxt(nxt),dist(dist){}
}edge[maxn*3*2*2];
int first[maxn*3],nume;
ll dist[maxn*3];bool vis[maxn*3];
void Addedge(int a,int b,ll c){
edge[nume] = Edge(b,first[a],c);
first[a] = nume++;
}
priority_queue<pair<ll,int> > Q;
void dijkstra(int S){
Rep(i,1,3*(W+1)*(H+1)) dist[i] = inf,vis[i] = false;
Q.push(pair<ll,int>(-0,S));dist[S] = 0;
while(!Q.empty()){
int u = Q.top().second;Q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(dist[v] > dist[u] + edge[e].dist){
dist[v] = dist[u] + edge[e].dist;
Q.push(pair<ll,int>(-dist[v],v));
}
}
}
}
const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
int front,rear,x[100005],y[100005],cc[1005][1005];
pii q[1005*1005];
inline int encode(int x,int y){return x * (W+1) + y + 1;}
signed main(){
H = rd(),W = rd();
A = rd(),B = rd(),C = rd();
n = rd();
//if(n==2) return 0;这句话为什么没用呀(mengbier
front = rear = 0;
mem(cc,-1);
Rep(i,1,n){
x[i] = rd(),y[i] = rd();
q[rear++] = {x[i],y[i]};
cc[x[i]][y[i]] = 0;
}
while(front < rear){
int x = q[front].fi,y = q[front].se;front++;
rep(d,0,4){
int xx = x + dx[d],yy = y + dy[d];
if(xx<0||xx>H||yy<0||yy>W) continue;
if(cc[xx][yy] == -1){
cc[xx][yy] = cc[x][y] + C;
q[rear++] = {xx,yy};
}
}
}
mem(first,-1);nume = 0;
Rep(i,0,H){
Rep(j,0,W){
rep(d,0,4){
int xx = i + dx[d],yy = j + dy[d];
if(xx<0||xx>H||yy<0||yy>W) continue;
Addedge(encode(i,j),encode(xx,yy),C);
}
Addedge(encode(i,j),encode(i,j)+BASE,B);
Addedge(encode(i,j)+BASE,encode(i,j),cc[i][j]);
if(i) Addedge(encode(i,j)+BASE,encode(i-1,j)+BASE,A);
if(i) Addedge(encode(i-1,j)+BASE,encode(i,j)+BASE,A);
Addedge(encode(i,j),encode(i,j)+2*BASE,B);
Addedge(encode(i,j)+2*BASE,encode(i,j),cc[i][j]);
if(j) Addedge(encode(i,j)+2*BASE,encode(i,j-1)+2*BASE,A);
if(j) Addedge(encode(i,j-1)+2*BASE,encode(i,j)+2*BASE,A);
}
}
dijkstra(encode(x[1],y[1]));
writeln(dist[encode(x[n],y[n])]);
}
文章目录
  1. 1. 题目
  2. 2. 吐槽
  3. 3. 题解