【BZOJ 1044】[HAOI2008]木棍分割

2019-11-08 03:04:50

字體：大中小

來源：轉載

供稿：網友

思路：

首先二分的答案，算出切m下，最長的一段的最短值。用動態規劃求方案數。設f[i][j] $f[i][j]$ 表示切了i $i$ 次，使用到了前j $j$ 個木段的方案數。狀態轉移方程： f[i][j]=∑f[i?1][k]→(1≤k≤j?1) $f[i][j]=/sum f[i-1][k]/to(1/le k/le j-1)$ 且(sum[j]?sum[k]≤ans) $(sum[j]-sum[k] /le ans)$ 對于初始的條件，顯然有f[0][1]=1 $f[0][1]=1$ 不難發現，k是隨著j的增長遞增的，所以用two pointer維護即可。對于空間，第一維的顯然可以滾掉。

代碼：

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 50010;const int p = 10007; int n, m, sm, mx;int val[maxn], sum[maxn];int f[2][maxn];bool check(int x){ int res = 0, tmp = 0; for(int i = 1; i <= n; i ++){ if(tmp + val[i] <= x) tmp += val[i]; else tmp = val[i], res ++; } return res <= m;}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%d", &val[i]), sm += val[i], mx = max(mx, val[i]); for(int i = 1; i <= n; i ++) sum[i] = sum[i-1] + val[i]; int l = mx, r = sm, ans = 0; while(l <= r){ int mid = (l+r) >> 1; if(check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } int now = 0, res = 0; for(int i = 1; sum[i] <= ans; i ++) f[now][i] = 1; for(int i = 1; i <= m; i ++){ int ll = 0, rr = 0, x = 0; now ^= 1; for(int j = 1; j <= n; j ++){ while(rr < j-1) x = ((x+f[now^1][++rr])%p+p)%p; while(sum[j]-sum[ll] > ans) x = ((x-f[now^1][ll++])%p+p)%p; f[now][j] = x; } res = (res+f[now][n])%p; }