题解 P2511 【[HAOI2008]木棍分割】
Piwry
2020-06-07 20:57:50
话说有一个 dp 很重要的（定义）细节都没人讲到...坑的我调了半天（
问题就出在 dp 式的定义中：其它题解应该是默认 $f[i][j]$ 代表取到第 $j$ 个，**严格**分 $i$ 块的方案数，并对每种块数的 $f[n]$ 求和统计答案。但我一开始思路~~比较清奇~~有点不一样：设 $f[i][j]$ 代表取到第 $j$ 个，**最多**分 $i$ 块的方案数，最后直接输出 $f[m+1][n]$ 就行了。
具体的来说，程序是（已按其他题解的方式优化，命名方式都差不多可以理解下...）：
```cpp
/*K[j] 表示最小的 k 满足 sum[j]-sum[k] < limit*/
for(int i =2; i <= m+1; ++i){
for(int j =1; j <= n; ++j){
/*k+1 到 j 都可以取并做一块，所以有可能用到 dp[i-1][k] 的情况，对应前缀和要再 -1*/
if(K[j]-1 > 0) dp[j] =(sdp[j]/*注意这里不是 j-1*/-sdp[K[j]-1 /*<-*/]+M)%M;
else dp[j] =sdp[j];
}
for(int j =1; j <= n; ++j) sdp[j] =(sdp[j-1]+dp[j]+M)%M;/*求 dp 前缀和*/
}
printf("%d", dp[n]);
```
虽然表面上看 dp 转移式可能看不太出来 ~~（或者我的 "表面" 想得太少了（~~ ：$f[i][j]$ 是最多分 $i$ 块，所以当然可以不分并继承 $f[i-1][j]$。
于是答案就**多**了~~亿点点~~。
**呐这究竟错在哪里呢？**
实际上，这种 dp 方式会将**实质相同**的不划分方案重复计数：例如 $f[i][j]$ 继承 $f[i-1][j]$ 的方案，就相当于在所有原方案上**再分一块 $(j, j+1)$** 的空集。因这些空集的位置不同，这种 dp 方式也会将这些**仅仅是空集（可能多个）位置不同的方案算作不同的方案计数**。（有点绕，可以多读几次理解下）
---
（样例数据：）
```
3 2
1
1
10
```
具体地来讲，取样例数据（可见上）,当循环完 $i=2$ 时，$f[2][.]$ 的数组内容是 $0, 1, 2, 1$（下标从 $0$ 开始），这时还没问题。
而当计算 $i=3$ 时，对于 $f[3][3]$，按上面的 dp 转移式,它应该为 $f[2][2]+f[2][3]$。
此时 $f[2][2]$ 的方案为 $\{(1)(1), (1,1)()\}$；
而 $f[2][3]$ 的方案为 $\{(1,1)(10)\}$；
至于 $f[3][3]$ 的方案就是 $\{(1)(1)(10), (1,1)()(10), (1,1)(10)()\}$。
可以发现因为计算了有不同的空集位置的方案，导致答案增多了。
---
另外可能有人想到，如果是严格分为 $i$ 块的话，为什么（我下面的以及其他题解的）程序没有特判 $i > j$ 时的贡献？
对于一个不合法的 $f[i][j]$ 满足 $i > j$，设它能取到的贡献 $f[i-1][j']$，一定有 $j'<j$，也就是说有 $j'<i-1$。由此我们可以知道，**不合法的方案一定是由不合法的方案转移而来的，其贡献全由不合法的方案组成**。
而对于一个合法的方案 $f[i][j]$ 满足 $i \leqslant j$，设它能取到的贡献 $f[i-1][j']$，是有可能有 $i-1>j'$ 的。也就是说，**合法的方案有可能由不合法的方案转移而来，其贡献可能含有不合法的方案**。
因此我们只需关心**最初的不合法方案**，也就是 $f[1][0]$。它的缺省值应该是 $0$，于是我们就可以保证不合法的方案不会产生贡献。（可以去调试一下验证看看）
~~（这件事告诉我们将 dp 数组缺省设为 $0$ 可以省多少事...（bushi~~
~~（上面那句话有点结果主义...（~~
## CODE
```cpp
#include <cstdio>
#include <iostream>
using std::min;
const int MAXN =5e4+50, M =10007;
int n, m;
int dp[MAXN], sdp[MAXN], sum[MAXN], K[MAXN];
inline int read(){
int x =0; bool f =0; char c =getchar();
while(c < '0' || c > '9') (c == '-') ? f =1, c =getchar() : c =getchar();
while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (48^c), c =getchar();
return (f) ? -x : x;
}
inline bool calc(int limit){
int cnt =0, Sum =0;
for(int i =1; i <= n; ++i){
if(Sum+sum[i]-sum[i-1] > limit) Sum =0, ++cnt;
if(cnt > m) return 0;
Sum +=sum[i]-sum[i-1];
}
if(Sum > limit) return 0;/*考虑单个元素大于 limit*/
else return 1;
}
int main(){
n =read(), m =read();
for(int i =1; i <= n; ++i) sum[i] =read(), sum[i] +=sum[i-1];
int l =0, r =sum[n], limit =0x7fffffff;
while(l <= r){
int mid =(l+r)>>1;
if(calc(mid)) limit =min(limit, mid), r =mid-1;
else l =mid+1;
}
for(int j =1, k =0; j <= n; ++j){
while(sum[j]-sum[k] > limit) ++k;/*k+1 至 j 的元素可以取并作为一块*/
K[j] =k;
}
for(int j =1; j <= n; ++j) sdp[j] =(sum[j] <= limit)+sdp[j-1];
int ans =(sdp[n]-sdp[n-1])%M;
for(int i =2; i <= m+1; ++i){
for(int j =1; j <= n; ++j){/*k+1 至 j 的元素，所以 f[i-1][k] 的贡献也要算，那么前缀和就要 -1*/
if(K[j]-1 > 0) dp[j] =(sdp[j-1]-sdp[K[j]-1 /*<-*/]+M)%M;
else dp[j] =sdp[j-1];
}
for(int j =1; j <= n; ++j) sdp[j] =(sdp[j-1]+dp[j]+M)%M;
(ans +=dp[n])%=M;
}
printf("%d %d", limit, ans);
}
```