题解 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] 就行了。

具体的来说，程序是（已按其他题解的方式优化，命名方式都差不多可以理解下...）：

/*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 方式也会将这些仅仅是空集（可能多个）位置不同的方案算作不同的方案计数。（有点绕，可以多读几次理解下）

（样例数据：）

具体地来讲，取样例数据（可见上）,当循环完 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

#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);
}