Đề bài: http://vn.spoj.com/problems/VOMARIO/
Thuận toán: Sử dụng Interval Tree để quản lí tập các đoạn thẳng. Có thể dễ dàng tìm được công thức QHĐ O(N^2) với F(i) = số năng lượng max đến lượt chơi thứ i. Để giảm độ phức tạp thì có thể dùng IT để cập nhật nhanh.
Code:
#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 2;
const int INF = 1e9 + 7;
using namespace std;
int n;
long long x[MAXN], w[MAXN], e[MAXN], a[MAXN], v[MAXN], b[MAXN];
long long f[MAXN];
struct line{
long long a, b;
} it[MAXN * 4];
long long Get(line d, long long pos)
{
return d.a * v[pos] + d.b;
}
long long query(int x, int l, int r, long long pos)
{
//cout << it[x].a<<" "<<it[x].b<<" :"<<l<<" "<<r<<endl;
if (pos < l || pos > r) return 0;
long long ans = Get(it[x], pos);
if (l == r) return ans;
int mid = (l + r) / 2;
ans = max(ans, query(2 * x, l, mid, pos));
ans = max(ans, query(2 * x + 1, mid + 1, r, pos));
return ans;
}
void update(int x, int l, int r, int u, int v, line val)
{
int mid = (l + r) / 2;
if (r < u || v < l) return;
if (u <= l && r <= v){
// do something
if (Get(it[x], l) >= Get(val, l) && Get(it[x], r) >= Get(val, r)){
return;
}
if (Get(it[x], l) <= Get(val, l) && Get(it[x], r) <= Get(val, r)){
it[x] = val;
return;
}
if (Get(it[x], l) >= Get(val, l) && Get(it[x], mid) >= Get(val, mid)){
update(2 * x + 1, mid + 1, r, u, v, val);
return;
}
if (Get(it[x], l) <= Get(val, l) && Get(it[x], mid) <= Get(val, mid)){
update(2 * x + 1, mid + 1, r, u, v, it[x]);
it[x] = val;
return;
}
if (Get(it[x], mid + 1) >= Get(val, mid + 1) && Get(it[x], r) >= Get(val, r)){
update(2 * x, l, mid, u, v, val);
return;
}
if (Get(it[x], mid + 1) <= Get(val, mid + 1) && Get(it[x], r) <= Get(val, r)){
update(2 * x, l, mid, u, v, it[x]);
it[x] = val;
return;
}
}
update(2 * x, l, mid, u, v, val);
update(2 * x + 1, mid + 1, r, u, v, val);
}
map<long long, long long> M;
long long pos[MAXN];
void trau()
{
f[0] = 0;
FORE(i, 1, n) FORE(j, 0, i - 1) if (f[j] >= w[j] * abs(x[i] - x[j]))
f[i] = max(f[i], f[j] - w[j] * abs(x[i] - x[j]) + e[i]);
cout << f[n] << endl;
//FORE(i, 1, n) cout << f[i]<<" ";cout<<endl;
memset(f, 0, sizeof(f));
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("VOMARIO.inp", "r", stdin);
freopen("VOMARIO.out", "w", stdout);
#endif //yeulaptrinh.de
cin >> n;
FORE(i, 1, n){
cin >> x[i] >> w[i] >> e[i];
a[i] = x[i];
}
//trau();
sort(a, a + n + 1);
FORE(i, 0, n) b[i] = lower_bound(a, a + n + 1, x[i]) - a;
FORE(i, 0, n) v[b[i]] = x[i], M[x[i]] = b[i];
FORE(i, 0, n) pos[i] = M[a[i]];
int top = *max_element(b, b + n + 1);
FORE(i, 1, MAXN * 4 - 1) it[i].a = 0, it[i].b = 0;
update(1, 0, top, 0, top, (line){0, 0});
//FORE(i, 1, n + 1) cout << b[i] <<" "<<v[b[i]]<<endl;
//FORE(i, 1, n + 1) cout<<a[i]<<" ";cout<<endl;
//b[0] = b[n + 1];
/*
update(1, 0, top, 0, 2, (line){-1, -1});
update(1, 0, top, 0, 0, (line){1, 9});
update(1, 0, top, 5, 5, (line){-4, 26});
update(1, 0, top, 5, 5, (line){4, -6});
cout << top << endl;
cout << query(1, 0, top, 2)<<"wtf"<<endl;
*/
//FORE(i, 0, n) cout << a[i]<<" ";cout<<endl;
//FORE(i, 0, n) cout << b[i]<<" ";cout<<endl;
long long ans = 0;
FORE(i, 1, n){
f[i] = query(1, 0, top, b[i]) + e[i];
ans = max(ans, f[i]);
long long l, r;
if (w[i] == 0) r = top, l = 0;
else{
//if (i == 2) cout << (x[i] + f[i] / w[i])<<"wtf"<<endl;
r = upper_bound(a, a + n + 1, x[i] + f[i] / w[i]) - a - 1;
//cout << x[i] + f[i] / w[i]<<"???"<<r<<"<<<<<"<<b[r]<<endl;
r = pos[r];
l = lower_bound(a, a + n + 1, x[i] - f[i] / w[i]) - a;
l = pos[l];
//cout <<l<<" "<<r<<endl;
}
long long mid = b[i];
update(1, 0, top, mid, r, (line){-w[i], f[i] + w[i] * x[i]});
update(1, 0, top, l, mid, (line){w[i], f[i] - w[i] * x[i]});
//cout<<i<<"=+"<<b[i]<<"??"<<f[i]<<endl;
//cout << mid <<" "<<r<<"line"<<-w[i]<<" "<<f[i] + w[i] * x[i]<<endl;
//cout << l <<" "<<mid<<"line"<<w[i]<<" "<<f[i] - w[i] * x[i]<<endl;
}
cout << ans;
return 0;
} |
Recent Comments