來到機房刷了一道水（bian’tai）題。題目思想非常簡單易懂（我的做法實際上參考了Evensgn 範學長，在此多謝範學長了） 題目擺上： 1044: [HAOI2008]木棍分割 Description 有n根木棍, 第i根木棍的長度為Li,n根木棍依次連結了一起, 總共有n-1個連接處. 現在允 ...
來到機房刷了一道水（bian’tai）題。題目思想非常簡單易懂（我的做法實際上參考了Evensgn 範學長，在此多謝範學長了）
題目擺上：
1044: [HAOI2008]木棍分割
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3162 Solved: 1182
[Submit][Status][Discuss]
Description
有n根木棍, 第i根木棍的長度為Li,n根木棍依次連結了一起, 總共有n-1個連接處. 現在允許你最多砍斷m個連
接處, 砍完後n根木棍被分成了很多段,要求滿足總長度最大的一段長度最小, 並且輸出有多少種砍的方法使得總長
度最大的一段長度最小. 並將結果mod 10007。。。
Input
輸入文件第一行有2個數n,m.接下來n行每行一個正整數Li,表示第i根木棍的長度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.
Output
輸出有2個數, 第一個數是總長度最大的一段的長度最小值, 第二個數是有多少種砍的方法使得滿足條件.
Sample Input
3 21
1
10
Sample Output
10 2HINT
兩種砍的方法: (1)(1)(10)和(1 1)(10)
多謝範學長的博客教會了我這道DP的優化。 接下來說說這道題的思路： 首先我們需要求被分割後的最長的木條的長度，這個很簡單，二分+貪心check即可，跟基本的套路一樣，相信大家都能理解：
bool check(int x/*x表示我們二分的最長段的長度*/){ if(x < p)return false; int cut = 0,add = 0; for(int i = 1;i <= n;++i){ if(add + a[i] > x){ cut++;//cut表示當前已經分割了幾次 if(cut > m)return false; add = 0; } add += a[i]; } return true; } while(l <= r){ mid = (l + r) >> 1; if(check(mid))r = mid - 1; else l = mid + 1; }
接下來求完了我們需要的len，就應該求有多少種方案可以滿足len了。
眾所周知，動態規劃的第一步是要寫出狀態……然後再來搞
我們設f[i][j]表示前i段一共分割了j次，設ss[i]為a[i]的首碼和，然後寫出dp方程：
f[i][j] = Σf[k][j-1] 其中k要滿足的條件是(1 <= k < i) && (ss[i] - ss[k] <= len)（這是很容易從題目中得出的）。
於是我們就可以完成了。
但是這樣也太簡單了吧……畢竟是HAOI的題目，如果這麼簡單就是NOIP難度了（雖然本人不否認以前的省選題目也有NOIP難度的）
然後註意到數據範圍：n<=50000,0<=m<=min(n-1,1000)
我們註意到我們程式的時間複雜度實際上是O(n^2 m) 的，這明顯就是爆了時間的。
那然後該怎麼辦呢？
我們可以註意到，如果我們設sumf 表示枚舉到k的時候Σf[k][j-1]，(1 <= k < i) && (ss[i] - ss[k] <= len)，mink表示滿足(1 <= k < i) && (ss[i] - ss[k] <= len)的最小的k。
其實對於 f[i][Now] ，其實是 f[mink][Last]...f[i-1][Last] 這一段 f[k][Last] 的和，mink 是滿足 Sum[i] - Sum[k] <= Len 的最小的 k ，對於從 1 到 n 枚舉的 i ，相對應的 mink 也一定是非遞減的（因為 Sum[i] 是遞增的）。我們記錄下 f[1][Last]...f[i-1][Last] 的和 Sumf ，mink 初始設為 1，每次對於 i 將 mink 向後推移，推移的同時將被捨棄的 p 對應的 f[p][Last] 從 Sumf 中減去。那麼 f[i][Now] 就是 Sumf 的值。（此段複製自Evensgn的博客，因為我覺得自己可能寫不出來這麼詳細）
這樣我們就不必枚舉k，時間複雜度就降低到可以接受的O(nm)了。
但是這樣就完成了？別天真了，還有一個坑那，時間解決了，空間呢？我們的空間複雜度是O(nm)啊，用計算器算一下明顯超了。
這時候的DP有一個技巧（類似於飛揚的小鳥NOIP2014），我們發現其實j所屬的那一維，只能由j-1轉移而來，所以可以使用最常用的手段——滾動數組，來滾動掉第二維
使用now和pre，f[maxn][2]，now和pre只能為0或1，且pre = now^1，每完成一遍外層m迴圈更新now ^= 1,pre = now^1。
這樣子我們的空間複雜度也降到可以接受的O（n）辣！
終於完成了，接下來就是代碼了：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <cstdlib> 6 #include <algorithm> 7 using namespace std; 8 const int maxn = 50005; 9 const int maxm = 1005; 10 const int mod = 10007; 11 int get_num(){ 12 int num = 0; 13 char c; 14 bool flag = false; 15 while((c = getchar()) == ' ' || c == '\r' || c == '\n'); 16 if(c == '-') 17 flag = true; 18 else num = c - '0'; 19 while(isdigit(c = getchar())) 20 num = num * 10 + c - '0'; 21 return (flag ? -1 : 1)*num; 22 } 23 int n,m; 24 int a[maxn],ss[maxn]; 25 int f[maxn][2]; 26 int now,pre,len,p = 0,mid,ans = 0; 27 bool check(int x){ 28 if(x < p)return false; 29 int cut = 0,add = 0; 30 for(int i = 1;i <= n;++i){ 31 if(add + a[i] > x){ 32 cut++; 33 if(cut > m)return false; 34 add = 0; 35 } 36 add += a[i]; 37 } 38 return true; 39 } 40 int main(){ 41 memset(f,0,sizeof(f)); 42 memset(a,0,sizeof(a)); 43 memset(ss,0,sizeof(ss)); 44 n = get_num(); 45 m = get_num(); 46 for(int i = 1;i <= n;++i){ 47 a[i] = get_num(); 48 ss[i] = a[i] + ss[i-1]; 49 p = max(p,a[i]); 50 } 51 int l = 0,r = 50000000; 52 while(l <= r){ 53 mid = (l + r) >> 1; 54 if(check(mid))r = mid - 1; 55 else l = mid + 1; 56 } 57 len = r + 1; 58 now = 0; 59 pre = now^1; 60 int sumf = 0; 61 int mink = 0; 62 for(int i = 0;i <= m;++i){ 63 sumf = 0; 64 mink = 1; 65 for(int j = 1;j <= n;++j){ 66 if(i == 0) 67 if(ss[j] <= len)f[j][now] = 1; 68 else f[j][now] = 0; 69 else{ 70 while(mink < j && ss[j] - ss[mink] > len){ 71 sumf -= f[mink][pre]; 72 sumf = (sumf + mod) % mod; 73 mink++; 74 } 75 f[j][now] = sumf; 76 } 77 sumf += f[j][pre]; 78 sumf %= mod; 79 } 80 ans += f[n][now]; 81 ans %= mod; 82 now ^= 1; 83 pre = now ^ 1; 84 } 85 printf("%d %d\n",len,ans); 86 return 0; 87 }
附贈一張圖片：
