[WF2011] MachineWorks（李超树优化dp）

[WF2011]MachineWorks

problem

BZOJ3963

solution

来得比较快的是，直接设 $d{p}_{i,j}:$ 考虑第 $j$ 天换购 $i$ 机器。

但是马上注意到天数是 $1e9$ 级别的，而机器是 $1e5$ 级别。

稍微想想，就能知道，因为每天机器只能在那一天买，而为了最大化利益，肯定不可能买了一台机器在换购下一台机器前就卖了。

所以真正有用的只有 $n$ 天——离散化！！

因为机器过了那天就不能买了，所以将机器按照购买天数升序排序。

考虑 $d{p}_i:$ 当前以 $i$ 机器执行转型期的已知利润最大值。

有两种情况：

• case1：就是前面一台机器都没买，用最开始的钱购买这一台机器开始赚钱，比较简单。

• case2：考虑在换购这一台机器前是用的机器 $j$。

  则有转移：$d{p}_i=\max \{d{p}_j+G_j(D_i-D_j-1)+R_j-P_i\}$

  整理一下得到，$d{p}_i=\max \{-G_j\cdot D_i+d{p}_j-G_j(D_j+1)+R_j\}-P_i$

然后要用 $d{p}_i$ 去更新最后的答案，$d{p}_i$ 是已知的利润，最后的答案就是假设这个机器不再改变。

即 $ans=max\{d{p}_i+(T-D_i)G(i)+R(i)\}$。

当然要满足 前面赚的钱 / 最开始的钱 能够买得起这件机器，再更新，否则会出错。

比如这台机器赚的利润非常高，结果买不起，答案可能会被这台压根买不了的机器利润更新成最大值。

$d{p}_i$ 的转移式子简直不能太熟悉了！

因为 $G$ 不具有单调性，所以不能斜率优化。

就算能，李超树不香吗？？只要不会超时，宁可死也要用李超不用斜率优化。

将 $-G_j$ 当成 $k$，$d{p}_j-G_j(D_j+1)+R_j$ 当成 $b$，每次以 $D_i$ 查。

code

#include <bits/stdc++.h> using namespace std; #define maxn 100005 #define int long long int n, C, T; int d[maxn], f[maxn]; struct Node { int D, P, R, G; }v[maxn]; struct node { int k, b; }t[maxn << 2];#define lson now << 1 #define rson now << 1 | 1 #define mid ( ( l + r ) >> 1 )int calc( node l, int x ) { return l.k * d[x] + l.b; }bool cover( node Old, node New, int x ) {return calc( Old, x ) <= calc( New, x ); }void insert( int now, int l, int r, node New ) {if( cover( t[now], New, l ) and cover( t[now], New, r ) ) {t[now] = New;return;}if( l == r ) return;if( cover( t[now], New, mid ) ) swap( t[now], New );if( cover( t[now], New, l ) ) insert( lson, l, mid, New );if( cover( t[now], New, r ) ) insert( rson, mid + 1, r, New ); }int query( int now, int l, int r, int x ) {if( ! t[now].k and ! t[now].b ) return 0;if( l == r ) return calc( t[now], x );int ans;if( x <= mid ) ans = query( lson, l, mid, x );else ans = query( rson, mid + 1, r, x );return max( ans, calc( t[now], x ) ); }signed main() {int Case = 0;while( scanf( "%lld %lld %lld", &n, &C, &T ) ) {if( ! n and ! C and ! T ) break;memset( t, 0, sizeof( t ) );memset( f, 0, sizeof( f ) );int ans = C;for( int i = 1, D, P, R, G;i <= n;i ++ ) {scanf( "%lld %lld %lld %lld", &D, &P, &R, &G );v[i] = { D, P, R, G };d[i] = D;}sort( d + 1, d + n + 1 );sort( v + 1, v + n + 1, []( Node x, Node y ) { return x.D < y.D; } );int m = unique( d + 1, d + n + 1 ) - d - 1;for( int i = 1;i <= n;i ++ ) v[i].D = lower_bound( d + 1, d + m + 1, v[i].D ) - d;for( int i = 1;i <= n;i ++ ) {int x = max( query( 1, 1, m, v[i].D ), C );if( x >= v[i].P ) {f[i] = x - v[i].P + v[i].R;ans = max( ans, f[i] + v[i].G * ( T - d[v[i].D] ) );insert( 1, 1, m, { v[i].G, f[i] - ( d[v[i].D] + 1 ) * v[i].G } );}}printf( "Case %lld: %lld\n", ++ Case, ans );}return 0; }

总结

以上是生活随笔为你收集整理的[WF2011] MachineWorks（李超树优化dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。