ABC209F. Deforestation——DP（、数学容斥）
题面
有
n
n
n 棵树排成一排，每棵树高度为
h
i
(
i
∈
[
1
,
n
]
)
h_i~(i\in[1,n])
hi (i∈[1,n]) ，你现在要按照一个排列
P
P
P 的顺序去砍树，每砍一棵树，这棵树的高度就会变成
0
0
0 ，也就是说，砍一棵树
i
i
i 会使得
h
i
→
0
h_i\rightarrow0
hi→0 。由于光头强的阻挠，你每次砍树的代价是当前这棵树相邻两棵树的高度加上这棵树的高度，即
h
i
−
1
+
h
i
+
h
i
+
1
h_{i-1}+h_i+h_{i+1}
hi−1+hi+hi+1 。
求有多少种不同的排列
P
P
P 能保证总代价最小，取模
998
244
353
998\,244\,353
998244353。
1
≤
n
≤
4000
,
1
≤
h
i
≤
1
0
9
1\leq n\leq4000,1\leq h_i\leq10^9
1≤n≤4000,1≤hi≤109 .
题解
我们把排列投射到这一排树上，每个位置记录自己被砍的次序
p
i
p_i
pi 。
那么除了自己被砍时被算进去的代价，额外代价（因砍伐邻居而付出的代价）就可以用
p
p
p 来判断。对于每个
i
∈
[
1
,
n
)
i\in[1,n)
i∈[1,n) ，若
p
i
<
p
i
+
1
p_i<p_{i+1}
pi<pi+1 ，则额外代价加上
h
i
+
1
h_{i+1}
hi+1 ，若
p
i
>
p
i
+
1
p_i>p_{i+1}
pi>pi+1 则额外代价加上
h
i
h_i
hi 。
现在我们看看，该怎么安排
p
i
p_i
pi ，使得总代价最小呢？
对于每个
i
∈
[
1
,
n
)
i\in[1,n)
i∈[1,n) ，如果
h
i
<
h
i
+
1
h_i<h_{i+1}
hi<hi+1 ，那么限制
p
i
>
p
i
+
1
p_i>p_{i+1}
pi>pi+1 ；如果
h
i
>
h
i
+
1
h_i>h_{i+1}
hi>hi+1 ，那么限制
p
i
<
p
i
+
1
p_i<p_{i+1}
pi<pi+1 。如果
h
i
=
h
i
+
1
h_i=h_{i+1}
hi=hi+1 ，相对大小无所谓了，不限制。这样下来，排列
p
p
p 就能使得总代价最小，满足所有限制条件的排列
p
p
p 的个数就是答案了。
那么就是一个经典问题：限制一个排列
p
p
p 相邻两位的大小关系，问总的排列个数。
如果是
n
≤
1
0
5
n\leq10^5
n≤105 级别的数据，要用比较复杂难懂的容斥来做，假定一段同向，然后减去不合法。
可喜(惜)的是，这道题
n
≤
4000
n\leq4000
n≤4000 ，可以
Θ
(
n
2
)
\Theta(n^2)
Θ(n2) 做。我们定义一个简单的
D
P
\rm DP
DP ，令
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示安排到第
i
i
i 位，前面有
j
j
j 个数比
p
i
p_i
pi 小的方案数。转移如下：
- p
i
>
p
i
−
1
p_i>p_{i-1}
pi>pi−1 ：
d
p
[
i
]
[
j
]
=
∑
k
=
0
j
−
1
d
p
[
i
−
1
]
[
k
]
dp[i][j]=\sum_{k=0}^{j-1}dp[i-1][k]
dp[i][j]=∑k=0j−1dp[i−1][k]
- p
i
<
p
i
−
1
p_i<p_{i-1}
pi<pi−1 ：
d
p
[
i
]
[
j
]
=
∑
k
=
j
i
−
2
d
p
[
i
−
1
]
[
k
]
dp[i][j]=\sum_{k=j}^{i-2}dp[i-1][k]
dp[i][j]=∑k=ji−2dp[i−1][k]
- (
e
m
p
t
y
)
({\rm empty})
(empty) ：
d
p
[
i
]
[
j
]
=
∑
k
=
0
i
−
2
d
p
[
i
−
1
]
[
k
]
dp[i][j]=\sum_{k=0}^{i-2}dp[i-1][k]
dp[i][j]=∑k=0i−2dp[i−1][k]
裸的前缀和优化，复杂度
Θ
(
n
2
)
\Theta(n^2)
Θ(n2) 。
CODE
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 4005
#define LL long long
#define DB double
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
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 x * f;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
int a[MAXN];
int dp[MAXN][MAXN];
int sum[MAXN][MAXN],suf[MAXN][MAXN];
int main() {
n = read();
for(int i = 1;i <= n;i ++) {
a[i] = read();
}
dp[0][0] = 1;
sum[0][0] = suf[0][0] = 1;
for(int i = 1;i <= n;i ++) {
for(int j = 0;j < i;j ++) {
if(a[i] > a[i-1]) {
dp[i][j] = suf[i-1][j];
}
else if(a[i] < a[i-1]) {
if(j > 0) dp[i][j] = sum[i-1][j-1];
}
else dp[i][j] = suf[i-1][0];
}
sum[i][0] = dp[i][0];
suf[i][i-1] = dp[i][i-1];
for(int j = 1;j < i;j ++) sum[i][j] = (sum[i][j-1] + dp[i][j]) % MOD;
for(int j = i-2;j >= 0;j --) suf[i][j] = (suf[i][j+1] + dp[i][j]) % MOD;
}
int ans = suf[n][0];
printf("%d\n",ans);
return 0;
}
最新文章
- Selenium 面试题总结（乙醇Blog记录的面试题）
- Shell 语法之结构化命令(流程控制)
- Ranorex入门指南
- CSS 实现加载动画之八-圆点旋转
- Java异常分类
- jquery 学习
- 学习心得记录：[一]sql安装与配置
- SRM 581 D2 L3：TreeUnionDiv2，Floyd算法
- 自己动手写CPU之第五阶段（3）——MIPS指令集中的逻辑、移位与空指令
- 精通Activity
- 邀请朋友富途开户赢iPhone6的史上最强攻略
- [Usaco2008 Open] Clear And Present Danger 寻宝之路[最短路][水]
- 手机自动化测试：appium源码分析之bootstrap十二
- python 发送163邮件
- WebApi上传文件
- 求矩形面积（问题来自PythonTip）
- Web安全学习笔记之更新kali国内源
- vue数据请求显示loading图
- Oracle12c 中RAC功能增强新特性之ASM&amp;Grid
- scala-学习 1