ABC 203 F - Weed （DP）
ABC203F - Weed
题意转述
S
t
e
v
e
\rm Steve
Steve 和
A
l
e
x
\rm Alex
Alex 正在下界(
N
e
t
h
e
r
l
e
n
d
\rm Netherlend
Netherlend)玩音符盒(
N
o
t
e
b
l
o
c
k
\rm Note~block
Note block)。
S
t
e
v
e
\rm Steve
Steve 和
A
l
e
x
\rm Alex
Alex 按下了按钮，听着各色音符被发光的红石线激活，感到无比欢乐。但是他们发现有的音符盒发不出声音，原因是被垂泪藤占据了上方的空气方块。于是
S
t
e
v
e
\rm Steve
Steve 和
A
l
e
x
\rm Alex
Alex 打算清除这些垂泪藤。他们是这样清除的：
- （为了有效地清除垂泪藤，他们打算到垂泪藤上方，挖掉它们上面的方块，除根）
- S
t
e
v
e
\rm Steve
Steve 先记下了其中至多
K
K
K 条垂泪藤，上去挖掉了它们上面的方块，清除它们。
- A
l
e
x
\rm Alex
Alex 重复进行这样的操作，直到所有垂泪藤被清除完： 找到长度最大的一条未除掉的垂泪藤的长度
H
H
H ，告诉
S
t
e
v
e
\rm Steve
Steve 所有未除掉的长度大于
H
2
\frac{H}{2}
2H 的垂泪藤的位置，然后让他除掉它们。
S
t
e
v
e
\rm Steve
Steve 想让
A
l
e
x
\rm Alex
Alex 进行的操作次数最少，在这个前提下，自己一开始记忆的垂泪藤数(
≤
K
\leq K
≤K)尽可能少。但是一共有
N
(
≤
2
⋅
1
0
5
)
N(\leq2\cdot10^5)
N(≤2⋅105) 条长度
h
i
≤
1
0
9
h_i\leq10^9
hi≤109 的垂泪藤（有个强大的模组消除了高度限制），于是
S
t
e
v
e
\rm Steve
Steve 想先向你询问，满足他的要求的情况下，
A
l
e
x
\rm Alex
Alex 进行的操作数和自己一开始记忆的垂泪藤数分别是多少。
题解
由于每次操作过后，最长的垂泪藤长度都至少会减半，因此，总操作数一定不会超过
log
H
m
a
x
+
1
=
31
\log H_{max}+1=31
logHmax+1=31，那么我们就可以用一个简单的
D
y
n
a
m
i
c
P
r
o
g
r
a
m
m
i
n
g
\rm Dynamic~Programming
Dynamic Programming 来解决这道题：
先把所有的垂泪藤按长度从小到大排序，令
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示以第
j
j
j 条垂泪藤为最长开始，进行了
i
i
i 次操作后，清除的最大可能条数(
d
p
[
0
]
[
0
]
=
0
dp[0][0]=0
dp[0][0]=0)。有如下转移：
d
p
[
i
]
[
j
]
=
max
2
h
k
≤
h
j
d
p
[
i
−
1
]
[
k
]
+
∑
2
h
k
>
h
j
,
k
≤
j
1
dp[i][j]=\max_{2h_k\leq h_j} dp[i-1][k]+\sum_{2h_k>h_j,k\leq j}1
dp[i][j]=2hk≤hjmaxdp[i−1][k]+2hk>hj,k≤j∑1
这个可以通过预处理以及前缀和优化等方式达到
O
(
1
)
O(1)
O(1) 转移，也当然可以用滚动少掉一维。
如果找到了最小的
i
i
i ，使得
d
p
[
i
]
m
a
x
≥
N
−
K
dp[i]_{max}\geq N-K
dp[i]max≥N−K，那么就可以输出
i
i
i 和
N
−
d
p
[
i
]
m
a
x
N-dp[i]_{max}
N−dp[i]max 了。
开头可以加个
k
=
n
k=n
k=n 的特判。
CODE
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define DB double
#define LL long long
#define ENDL putchar('\n')
#define lowbit(x) ((-x) & (x))
#define INF 0x3f3f3f3f
LL read() {
LL f=1,x=0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
int a[MAXN];
int dp[2][MAXN];
int main() {
n = read();k = read();
for(int i = 1;i <= n;i ++) {
a[i] = read();
}
if(k == n) {printf("0 %d\n",n);return 0;}
sort(a + 1,a + 1 + n);
int ans = 0;
for(int i = 1;i <= 32;i ++) {
int ad = 0,mx = 0;
for(int j = 1;j <= n;j ++) {
while(ad < n && a[ad+1] <= a[j]/2) mx = max(mx,dp[i&1^1][++ ad]);
dp[i&1][j] = mx + (j-ad);
ans = max(dp[i&1][j],ans);
}
if(ans >= n-k) {printf("%d %d\n",i,n-ans);return 0;}
}
return 0;
}
最新文章
- 通过FileHandle获取FileObject对象
- 【JavaScript】【CSS】前端规则摘抄
- CSS轮廓outline
- VIM 中鼠标选择不选中行号
- ArcGIS 10 影像去黑边
- win7下VS.NET中通过LinqToSQL连接oracle数据库
- 代码编写横屏的UIView
- 值得关注的 10 个 Python 英文博客
- 1.Tomcat配置
- iocomp控件的应用
- 如何在Eclipse和MyEclipse中安装SVN
- 【3】docker命令集
- Entity Framework Core 生成跟踪列
- Vue工具
- RMAN-06900 RMAN-06901 ORA-19921
- git使用操作
- 数据分析常用的python工具和SQL语句
- HanLP 关键词提取算法分析详解
- DOM心得
- 【转】 js数组 Array 交集 并集 差集 去重