題意:n根木棍依次連在一起 最多切m個端點 使得最長的一段最小

　　 在保證最長的最小的情況下 有多少種不同的切法

題解:第一問傻子都知道二分

　　 第二問想了一會不會做 但其實就是很簡單的dp

　　 dp[i][j]表示切完第i刀切到第j段后面的的種數

　　 想了一下覺得空間過不去 然而這個是可以滾動的 因為每一刀的轉移都只和前一刀有關系 再優化下時間

　　 預處理一下last[i]表示在第i個木棍后面切的話 至少要在last[i]這個點及以后也切一下

　　 躍然紙上的轉移 dp[i][j] += dp[i - 1][k]? if(last[j] <= k < j) 但這是個接近n^3的復雜度

　　 然后發現每次轉移 dp[i][j]都是加的相同一段 所以我們可以每次前綴和搞一下

?

#include <bits/stdc++.h> using namespace std; const int mod = 10007;int n, m; int q[50005]; int sum[50005]; int last[50005]; int dp[2][50005]; int pre[2][50005]; int ans1, ans2;int check(int x) {int res = 0;int cnt = 0;for(int i = 1; i <= n; i++){res += q[i];if(res > x) cnt++, res = q[i];}return cnt; }int main() {ans2 = 0;scanf("%d%d", &n, &m);int l = 0, r = 0;for(int i = 1; i <= n; i++){scanf("%d", &q[i]);l = max(l, q[i]); r += q[i];}int mid = l + r >> 1;while(l + 1 < r){mid = l + r >> 1;if(check(mid) <= m) ans1 = mid, r = mid;else l = mid;}if(check(l) <= m) ans1 = l;int zsum = 0;int p = 1;for(int i = 1; i <= n; i++){zsum += q[i];while(zsum > ans1) zsum -= q[p], p++;last[i] = p - 1;if(last[i] == 0) dp[1][i] = 1;}ans2 += dp[1][n];for(int i = 1; i <= n; i++) pre[1][i] = (dp[1][i] + pre[1][i - 1]) % mod;for(int i = 2; i <= m + 1; i++){memset(dp[i & 1], 0, sizeof(dp[i & 1]));pre[i & 1][i - 1] = 0;for(int j = i; j <= n; j++){dp[i & 1][j] = (dp[i & 1][j] + pre[(i - 1) & 1][j - 1]) % mod;if(last[j]) dp[i & 1][j] = (dp[i & 1][j] - pre[(i - 1) & 1][last[j] - 1]) % mod;dp[i & 1][j] = (dp[i & 1][j] + mod) % mod;}for(int j = i; j <= n; j++) pre[i & 1][j] = (pre[i & 1][j - 1] + dp[i & 1][j]) % mod;ans2 = (ans2 + dp[i & 1][n]) % mod;}printf("%d %d\n", ans1, ans2);return 0; } View Code

?

　　?

　　?

轉載于:https://www.cnblogs.com/lwqq3/p/9774514.html

總結

以上是生活随笔為你收集整理的BZOJ1044: [HAOI2008]木棍分割 (二分 + DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。