BZOJ1044: [HAOI2008]木棍分割(dp 单调队列)
程序员文章站
2022-11-08 22:10:46
题意 "题目链接" Sol 比较套路的一个题。 第一问二分答案check一下 第二问设$f[i][j]$表示前$i$个数,切了$j$段的方案数,单调队列优化一下。 转移的时候只需要保证当前段的长度小于最大限度即可。 cpp include using namespace std; const int ......
题意
sol
比较套路的一个题。
第一问二分答案check一下
第二问设\(f[i][j]\)表示前\(i\)个数,切了\(j\)段的方案数,单调队列优化一下。
转移的时候只需要保证当前段的长度小于最大限度即可。
#include<bits/stdc++.h> using namespace std; const int maxn = 50001, mod = 10007; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, a[maxn], sum[maxn]; int check(int val) { int tot = 0, pre = 0; for(int i = 1; i <= n; i++) { if(sum[i] - sum[pre] > val) { if((sum[i - 1] - sum[pre] <= val) && a[i] <= val) tot++, pre = i - 1; else return 0; } } return tot <= m; } int solve1() { int l = 0, r = sum[n], ans;//二分最大长度 while(l <= r) { int mid = l + r >> 1; if(check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } return printf("%d ", ans), ans; } int add(int x, int y) { if(x + y < 0) return x + y + mod; else return (x + y > mod ? x + y - mod : x + y); } int solve2(int mx) { static int f[maxn], g[maxn], q[maxn], ans = 0; // f[0][0] = 1; for(int i = 1; i <= n; i++) g[i] = (sum[i] <= mx); for(int j = 1; j <= m; j++) { for(int i = 1, h = 1, t = 0, s = 0; i <= n; i++) { while(h <= t && (sum[i] - sum[q[h]] > mx)) s = add(s, -g[q[h++]]); q[++t] = i; f[i] = s; s = add(s, g[i]); /* for(int k = i - 1; k >= 1; k--) { if(sum[i] - sum[k] <= mx) (f[i][j] += f[k][j - 1]) %= mod; else break; }*/ } ans = add(ans, f[n]); memcpy(g, f, sizeof(g)); } return ans % mod; } int main() { // freopen("10.in", "r", stdin); n = read(); m = read(); for(int i = 1; i <= n; i++) a[i] = read(), sum[i] = sum[i - 1] + a[i]; printf("%d", solve2(solve1())); }
下一篇: 结婚几年笑话真多