P5902 [IOI2009]salesman

部分分很好做。如果任意两个展会都不在同一天举行,也就是对展会按照时间进行排序后,问题就可以转化成选择一个子序列,使得最后的权值尽量大。而且不难发现新加入一个点只和之前最后的一个点的权值有关,可以很简单地写出方程:

然后可以分成从上游来还是从下游来:

拿两个 BIT 维护前后缀最大值即可。


考虑有很多展会在同一天举行。

稍微更改一下 $dp$ 数组的定义,设 $f[i]$ 表示已经结束了 $i$ 展会这一天的所有操作,最后在 $i$ 这个位置结束,所得到的最优收益。

这一天内的展会最后会得到访问的必然是一段区间,显然不选择区间一定可以把左右端点内的所有点都选上更优。于是,一天的决策一定是这两种:

image.png

也就是要么一路扫过去,要么扫过去再折回来。

开始思路就卡在这里了,不太清楚怎么 $dp$ 这个。其实场后觉得也很自然。由于我们需要求出的是每个这一天内的点作为结束点的时候的最优收益,我们可以先用线段树把红箭头的情况解决,也就是用类似部分分的方程解决从上一天的状态转移到这一天的某个位置,并且只通过向上或者向下的方向之一走。然后再做一次层内的 $dp$ ,设 $dp[i]$ 表示层内结束点是 $i$ ,由 $i$ 上游某个点转移过来的最小代价,同理设 $pd[i]$ 表示从下游转移。这里就可以把折线的情况考虑到了,虽然会重复计算同一个方案,但是可以算出最优的结果。

复杂度是 BIT 查前后缀最大值 $O(n \log n)$。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "string"
using namespace std;
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
typedef unsigned long long u64;
const int P = 924844033;
int n , U , D , s;

vector<pii> S[MAXN];
int dy , mx;
int dp[MAXN] , pd[MAXN] , f[MAXN];
struct BIT {
int T[MAXN];
BIT( ) { memset( T , -0x3f , sizeof T ); }
void pu( int x , int c ) {
while( x <= mx ) T[x] = max( T[x] , c ) , x += x & -x;
}
int pmx( int x ) {
int ret = -0x3f3f3f3f;
while( x > 0 ) ret = max( ret , T[x] ) , x -= x & -x;
return ret;
}
} T[2] ;

void solve() {
cin >> n >> U >> D >> s;
mx = s;
rep( i , 1 , n ) {
int t , l , m;
dy = max( dy , t );
scanf("%d%d%d",&t,&l,&m);
S[t].eb( mp( l , m ) );
mx = max( mx , l );
}
T[0].pu( s , s * D ) , T[1].pu( mx - s + 1 , - s * U );
S[dy + 1].eb( mp( s , 0 ) );
++ dy;
int res = 0;
rep( i , 1 , dy ) if( S[i].size() ) {
sort( all( S[i] ) );
int m = S[i].size();
for( int j = 1 ; j <= m ; ++ j ) {
pii u = S[i][j - 1];
f[j] = max( T[1].pmx( mx - u.fi + 1 ) + u.fi * U , T[0].pmx( u.fi ) - u.fi * D ) + u.se;
}
dp[1] = f[1];
rep( j , 2 , m ) dp[j] = max( f[j] , dp[j - 1] - D * ( S[i][j - 1].fi - S[i][j - 2].fi ) + S[i][j - 1].se );
pd[m] = f[m];
per( j , m - 1 , 1 ) pd[j] = max( f[j] , pd[j + 1] - U * ( S[i][j].fi - S[i][j - 1].fi ) + S[i][j - 1].se );
rep( j , 1 , m ) {
f[j] = max( pd[j] , dp[j] );
res = max( res , f[j] );
pii u = S[i][j - 1];
T[0].pu( u.fi , f[j] + u.fi * D ) , T[1].pu( mx - u.fi + 1 , f[j] - u.fi * U );
}
}
printf("%d\n",f[1]);
}

signed main() {
// freopen("sample_wave10.in","r",stdin);
// freopen("wave.out","w",stdout);
// freopen("28.in","r",stdin);
// freopen("sot","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2020/11/18/p5902-ioi2009salesman/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog