洛谷 P9102 [PA 2020] Cukierki 题解-171主机测评

原题目链接。

在洛谷上看此题解。

声明：本文章需经作者允许方可转载。

神奇的题目。

结论

设子集元素按非降序排列为

≤

⋯

≤

b_1 \\leq b_2 \\leq \\dots \\leq b_k

$b_{1} \leq b_{2} \leq \dots \leq b_{k}$ ，定义前缀和

s_0=0

$s_{0} = 0$ ，$s_i=b_1+b_2+\\dots+b_i $（即 $s_k=x $）。该子集是“好子集”的充要条件为：对所有

≤

1 \\leq i\\leq k

$1 \leq i \leq k$ ，满足

≤

−

b_i\\leq s_{i-1}+1

$b_{i} \leq s_{i - 1} + 1$ 。

下面提供两种证明：

反证法若存在某

$i$ 使得

−

b_i>s_{i-1}+1

$b_{i} > s_{i - 1} + 1$ ，则前

−

i-1

$i - 1$ 个元素最大可表示

−

s_{i-1}

$s_{i - 1}$ ，而

−

b_i>s_{i-1}+1

$b_{i} > s_{i - 1} + 1$ 意味着

−

s_{i-1}+1

$s_{i - 1} + 1$ 无法通过“前

−

i-1

$i - 1$ 个元素的组合”或“前

−

i-1

$i - 1$ 个元素的组合 +

b_i

$b_{i}$ ”得到（后者最小为

−

b_i>s_{i-1}+1

$b_{i} > s_{i - 1} + 1$ ），与“好子集”定义矛盾。

数学归纳法

k

=

1

k=1

$k = 1$

此时

b

1

≤

s

0

+

1

=

1

b_1\\leq s_0+1=1

$b_{1} \leq s_{0} + 1 = 1$ ，故

b

1

=

1

b_1=1

$b_{1} = 1$ ，子集总糖果数

x

=

1

x=1

$x = 1$ ，显然可表示

y

=

1

y=1

$y = 1$ ，满足“好子集”定义。
假设

k

=

i

−

1

k=i-1

$k = i - 1$ 成立，证

k

=

i

k=i

$k = i$ 成立

假设前

i

−

1

i-1

$i - 1$ 个元素可表示

[

1

,

s

i

−

1

]

[1,s_{i-1}]

$[1, s_{i - 1}]$ 中所有数。加入

b

i

b_i

$b_{i}$ 后，新前缀和

s

i

=

s

i

−

1

+

b

i

s_i=s_{i-1}+b_i

$s_{i} = s_{i - 1} + b_{i}$ 。对任意

y

∈

[

1

,

s

i

]

y\\in[1,s_i]

$y \in [1, s_{i}]$ ：
- 若 $y\\in[1,s_{i-1}] y∈[1,si−1]：由归纳假设，可通过前 i − 1 i-1 i−1 个元素表示；$
- 若 $y\\in[s_{i-1}+1,s_i] y∈[si−1+1,si]：则 y − b i ∈ [ s i − 1 + 1 − b i , s i − 1 ] y – b_i \\in[s_{i-1}+1-b_i,s_{i-1}] y−bi∈[si−1+1−bi,si−1]。由充要条件 b i ≤ s i − 1 + 1 b_i\\leq s_{i-1}+1 bi≤si−1+1，得 y − b i ≥ 0 y – b_i \\geq 0 y−bi≥0。若 y − b i = 0 y-b_i=0 y−bi=0，则直接取 b i b_i bi 即可；若 y − b i > 0 y-b_i>0 y−bi>0，则 y − b i ∈ [ 1 , s i − 1 ] y-b_i\\in[1,s_{i-1}] y−bi∈[1,si−1]，由归纳假设可表示，故 y = ( y − b i ) + b i y=(y-b_i)+b_i y=(y−bi)+bi 可表示。$

因此前

$i$ 个元素可表示

[

]

[1,s_i]

$[1, s_{i}]$ 中所有数。

思路

然后很明显使用动态规划。

首先将数组

$a$ 按非降序排列，因为处理元素时始终从最小未处理元素开始，这样就可以利用前缀和条件

≤

−

b_i\\leq s_{i-1}+1

$b_{i} \leq s_{i - 1} + 1$ （若当前元素已满足对当前前缀和的条件，那么后续更大元素无需额外判断）。

然后就是状态定义：设

dp_i

$d p_{i}$ 表示前缀和为

$i$ 的好子集数量。

注意这里有一个重要的优化点，由于

≤

5000

a_i \\leq 5000

$a_{i} \leq 5000$ ，当

≥

5000

s\\geq5000

$s \geq 5000$ 时，任意

≤

5000

≤

a_i\\leq5000\\leq s+1

$a_{i} \leq 5000 \leq s + 1$ （因

≥

5000

⟹

≥

5001

s\\geq5000\\implies s+1\\geq 5001>a_i

$s \geq 5000 ⟹ s + 1 \geq 5001 > a_{i}$ ），故所有

≥

5000

s\\geq5000

$s \geq 5000$ 的状态可合并为

5000

dp_{5000}

$d p_{5000}$ ，无需记录具体值。

转移方程，对每个元素

a_i

$a_{i}$ ，倒序遍历前缀和

$s$ ，避免重复计算，类似 01 背包：若

≥

−

s\\geq a_i-1

$s \geq a_{i} - 1$ （即

≤

a_i\\leq s+1

$a_{i} \leq s + 1$ ，满足充要条件），则可将

a_i

$a_{i}$ 加入前缀和为

$s$ 的好子集，新前缀和为

min

⁡

(

5000

)

\\min(s+a_i,5000)

$min (s + a_{i}, 5000)$ ，转移式为：

min

⁡

(

5000

)

(

min

⁡

(

5000

)

(

)

dp_{\\min(s+a_i,5000)}=(dp_{\\min(s+a_i,5000)}+ dp_s)\\bmod (10^9+7)

$d p_{m i n (s + a_{i}, 5000)} = (d p_{m i n (s + a_{i}, 5000)} + d p_{s}) mod (1 0^{9} + 7)$

注意边界

dp_0=1

$d p_{0} = 1$ 表示空集。

最终答案就是所有非空好子集的数量，即

∑

5000

(

)

\\sum_{s=1}^{5000} dp_s \\bmod (10^9+7)

$\sum_{s = 1}^{5000} d p_{s} mod (1 0^{9} + 7)$ （空集肯定是不计入，故从

s=1

$s = 1$ 开始累加）。

代码

试过了，填表法可能有问题，所以还是用刷表法吧。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,a[5001],dp[5005],ans;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=5000;j>=a[i]–1;j—){
dp[min(5000ll,a[i]+j)]=(dp[min(5000ll,a[i]+j)]+dp[j])%mod;
}
}
for(int i=1;i<=5000;i++)ans=(ans+dp[i])%mod;
cout<<ans;
}

洛谷 P9102 [PA 2020] Cukierki 题解

结论

思路

代码

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

结论

思路

代码

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发