珠宝

loj6039「雅礼集训 2017 Day5」珠宝

题目描述

题目链接

Miranda 准备去市里最有名的珠宝展览会，展览会有可以购买珠宝，但可惜的是只能现金支付，Miranda 十分纠结究竟要带多少的现金，假如现金带多了，就会比较危险，假如带少了，看到想买的右买不到。展览中总共有 \(n\) 种珠宝，每种珠宝都只有一个，对于第 \(i\) 种珠宝，它的售价为 \(c_i\) 万元，对 Miranda 的吸引力为 \(v_i\)。Miranda 总共可以从银行中取出 k 万元，现在她想知道，假如她最终带了 \(i\) 万元去展览会，她能买到的珠宝对她的吸引力最大可以是多少？

数据范围

\(1\le n\le 1000000,1\le k\le 50000,1\le c_i\le 300,0\le v_i \le 10^9\)。

题外话

这题是真恶心啊，真给我恶心到了。

解法

首先，注意到 \(c_i\) 的范围，只有 \(300\)，而物品有 \(10^5\) 个，所以我们可以先把所有价格相同的物品放到一起，然后先取价值 \(v_i\) 较大的。

可以用分组背包，然后对每个相同 \(c_i\) 的物品由价值从大到小排好序后做一个前缀和，设这个前缀和数组为 \(s_{i,j}\)，表示单个花费为 \(i\) 的前 \(j\) 个物品总共所需代价。

这里预处理部分复杂度为 \(O(n)\)，我代码中的为了后面好写，复杂度上界为 \(O(cn)\)。

自然而然，列出转移方程式。设 \(f_{i,j}\) 表示单个物品价格不超过 \(i\)，当前可使用费用为 j 所能获得的最大价值。

可得：\(f_{i,j}=\max{\{f_{i-1,j-k\times i}+s_{i,k}\}}\)。

观察这个方程，复杂度上界为 \(O(ckn)\)。这个复杂度显然不行（不过要是硬卡应该也是有可能能卡过去的）。

考虑优化。观察上面方程式的特点，右边那个 \(s_{i,k}\) 在每个 \(i\) 之间互不影响，并且随着 \(k\) 的增大它的增长率不断减小。

考虑如何利用这个特点，首先转换一下右边 \(f\) 的第二维下标，把它写成 \(k\) ，那么后边就变成了 \(s_{i,\frac{j-k}{i}}\) 。

原式就是：\(f_{i,j}=\max{\{f_{i-1,k}+s_{i,\frac{j-k\ }{\ i}}\}}\)。

我们发现其中 \(j\) 和 \(k\) 必须在模 \(i\) 相同的情况下时，原式才有意义，所以我们考虑枚举每个在模 \(i\) 后的剩余系。

关于这个东西，打个表就会发现，它具有决策单调性。这里的决策单调性是指在从 \(k\) 转移到 \(j\) 时具有单调性。

感性理解一下第二个式子的决策单调性。其实就是指在当前每个物品的价格为 \(i\) 的情况下，只有 模 \(i\) 相同 的两个状态，才可能会有 转移关系。如果在模 \(j\) 不同的情况下直接写了决策单调性，其实就是指第一个式子中的 \(j\) 具有单调性，这是错误的。

之后，这里的单调性也不是指每个模 \(i\) 相同的数之间，他们选择当前价值为 \(i\) 的物品 选了几个 具有单调性，即不是第一个式子中的 \(k\) 具有单调性。

不巧，上面两个错我都各犯了一遍/dk/dk/dk。

如果非要说第一个式子中的，其实是 \(j-k\times i\) 这个整体具有单调性。（可恶（雾。

好吧，之后就是正常的套板子了。一般来说决策单调性的写法就是利用单调队列（不过这题好像可以用分治写，不仅好写，而且 不容易犯错）。

整个的时间复杂度上界是 \(O(cn\log n)\)。

Code

#include 
#include 
#include 
using namespace std ;

#define int long long
const int N = 50005 ;
int n , k , f[N] , g[N] ;

vector < int > sc[305] , vc[305] ;

struct Node {
	int l , r , p ;
	Node ( int _l = 0 , int _r = 0 , int _p = 0 ) : l ( _l ) , r ( _r ) , p ( _p ) { }
} q[N] ;

inline bool cmp ( int a , int b ) {
	return a > b ;
}

inline int calc ( int i , int x , int y ) {
	if ( x < y )
		return -1 ;
	return g [ y ] + sc [ i ] [ ( x - y ) / i ] ;
}

bool cis[305] ;

int ot = 1 ;
signed main ( ) {
	cin >> n >> k ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		int x , y ;
		cin >> x >> y ;
		vc [ x ] .push_back ( y ) ;
	}
	for ( int i = 1 ; i <= 300 ; ++ i ) {
		if ( vc [ i ] .empty ( ) )
			continue ;
		sort ( vc [ i ] .begin ( ) , vc [ i ] .end ( ) , cmp ) ;
		int siz = vc [ i ] .size ( ) ;
		sc [ i ] .push_back ( 0 ) ;
		for ( int j = 0 ; j < siz ; ++ j )
			sc [ i ] .push_back ( sc [ i ] [ j ] + vc [ i ] [ j ] ) ;
		for ( int j = siz + 2 ; j <= k / i + 2 ; ++ j )
			sc [ i ] .push_back ( sc [ i ] .back ( ) ) ;
	}
	int kp = 300 ;
	for ( int i = 1 ; i <= kp ; ++ i ) {
		if ( vc [ i ] .empty ( ) )
			continue ;
		for ( int j = 1 ; j <= k ; ++ j )
			g [ j ] = f [ j ] ;
		for ( int d = 0 ; d < i ; ++ d ) {
			int head = 1 , tail = 1 ;
			q [ tail ] = Node ( d , k , d ) ;
			for ( int j = 0 , jd ; ( jd = j * i + d ) <= k ; ++ j ) {
				while ( head <= tail && q [ head ] .r < jd )
					++ head ;
				if ( q [ head ] .l < jd )
					q [ head ] .l = jd ;
				int ps = 0 ;
				while ( head <= tail && calc ( i , q [ tail ] .l , q [ tail ] .p ) < calc ( i , q [ tail ] .l , jd ) )
					ps = q [ tail -- ] .l ;
				if ( head <= tail && calc ( i , q [ tail ] .r , q [ tail ] .p ) < calc ( i , q [ tail ] .r , jd ) ) {
					int l = q [ tail ] .l , r = q [ tail ] .r , mid ;
					while ( l <= r ) {
						mid = ( l + r ) >> 1 ;
						if ( calc ( i , mid , q [ tail ] .p ) <= calc ( i , mid , jd ) )
							ps = mid , r = mid - 1 ;
						else
							l = mid + 1 ;
					}
					q [ tail ] .r = ps - 1 ;
				}
				if ( ps )
					q [ ++ tail ] = Node ( ps , k , jd ) ;
				f [ jd ] = calc ( i , jd , q [ head ] .p ) ;
			}
		}
	}
	for ( int i = 1 ; i <= k ; ++ i )
		cout << f [ i ] << " " ;
	cout << "\n" ;
	return 0 ;
}