「NOI模拟赛3.13」珠宝jewelry - 动态规划/背包+决策单调性 | Bill Yang's Blog

「NOI模拟赛3.13」珠宝jewelry - 动态规划/背包+决策单调性

题目大意

    Miranda 准备去市里最有名的珠宝展览会,展览会有可以购买珠宝,但可惜的是只能现金支付,Miranda十分纠结究竟要带多少的现金,假如现金带多了,就会比较危险,假如带少了,看到想买的右买不到。展览中总共有$N$种珠宝,每种珠宝都只有一个,对于第$i$种珠宝,它的售价为$C_i$万元,对Miranda的吸引力为$V_i$。Miranda总共可以从银行中取出$K$万元,现在她想知道,假如她最终带了$i$万元去展览会,她能买到的珠宝对她的吸引力最大可以是多少?
    $1\le N\le1000000,1\le K\le50000,1\le C_i\le300,0\le V_i\le10^9$


题目分析

本题就是一个0/1背包问题。
$0/1$背包问题的时间复杂度是$O(nk)$的,$n,k\le10000$可以过$20$分数据(没想到吧)。

考试时觉得不可思议,背包问题竟然还能优化?我觉得我总结的优化已经前路技穷了啊?
考试完后发现漏读了一个重要条件:$1\le C_i\le300$。

我们不妨将物品按照$C_i$分类。

设$Value[i,j]$表示代价为$i$的物品购买$j$个能获得的最大价值。
$f[i,j]$表示代价$\le i$的物品,花费代价为$j$能获得的最大价值。
先列出转移方程:

有没有发现这个式子和多重背包的式子谜之相似?
若$Value[i,k]=k\times g(i)$(其中$g(i)$是关于$i$的函数),则可以使用单调队列优化。
这也就是另外$20$分部分数据的做法。

考虑权函数$Value[i,j]$。
由于有$Value[i,j]-Value[i,j-1]\ge Value[i,j+1]-Value[i,j]$,因此权函数单调不增,呈上凸形式。
故方程具有决策单调性(打表也可发现)。

使用经典的1D/1D决策单调性优化动规即可,时间复杂度$O(300K\log K)$。


代码

又一次创造OJ最慢记录。
之前使用deque常数大得T了。
果然枚举剩余系常数很大。

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxk=50005;
LL cost,now,last,f[2][maxk];
vector<LL>Value[305];
LL Cal(int j,int k) {
if(j<k)return -LLONG_MAX/2;
return f[last][k]+Value[cost][(j-k)/cost];
}
int Binary(int Left,int Right,int x,int y) {
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Cal(mid,x)>Cal(mid,y))Left=mid+1;
else Right=mid-1;
}
return Right;
}
int n,k;
vector<int>Thing[305];
struct QueNode {
int pos,l,r;
QueNode(int p=0,int _l=0,int _r=0):pos(p),l(_l),r(_r) {}
} Q[maxk];
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
int c=Get_Int(),v=Get_Int();
Thing[c].push_back(v);
}
for(int i=1; i<=300; i++) {
sort(Thing[i].begin(),Thing[i].end(),greater<LL>());
Value[i].push_back(0);
for(int j=1; i*j<=k; j++)
if(j<=Thing[i].size())Value[i].push_back(Value[i].back()+Thing[i][j-1]);
else Value[i].push_back(Value[i].back());
}
for(cost=1; cost<=300; cost++) {
now=cost&1,last=now^1;
for(int mod=0; mod<cost; mod++) {
int Left=1,Right=1;
Q[Left]=QueNode(mod,0,k);
for(int i=0,index; (index=i*cost+mod)<=k; i++) {
while(Left<=Right&&Q[Left].r<index)Left++;
if(Left<=Right)Q[Left].l=index;
if(Left>Right||Cal(k,index)>Cal(k,Q[Right].pos)) {
while(Left<=Right&&Cal(Q[Right].l,index)>=Cal(Q[Right].l,Q[Right].pos))Right--;
if(Left>Right)Q[++Right]=QueNode(index,index,k);
else {
int pos=Binary(Q[Right].l,Q[Right].r,Q[Right].pos,index);
Q[Right].r=pos;
if(pos+1<=k)Q[++Right]=QueNode(index,pos+1,k);
}
}
if(Left<=Right)f[now][index]=Cal(index,Q[Left].pos);
}
}
}
for(int i=1; i<=k; i++) {
f[now][i]=max(f[now][i],f[now][i-1]);
printf("%lld ",f[now][i]);
}
return 0;
}

本篇文章有用吗?有用还不快点击!
0%