题意
多测。
给定 \(n\) 个字符串和一个常数 \(L\),试将这些字符串分成若干组,使得:
令 \(len(i)\) 为第 \(i\) 个字符串的长度,则每组字符串的 \(|\sum\limits len(i) - L|\) 的 \(P\) 次方和之和最小。
\(n \leq 10^5, L \leq 3 \times 10^6\),每个字符串的长度不超过 \(30\)
思路
决策单调性优化 dp.
分组问题,考虑决策单调性。大力瞪眼发现成立,证明。
状态:\(f[i]\) 表示前 \(i\) 个串的最优解。
转移:令 \(sum[i] = \sum\limits_{j = 1}^i len(i) + 1\),则 \(f[i] = \min\limits_{j = 0}^{i - 1} f[j] + |sum_i - sum_j - L - 1|^P\)
然后考虑用二分队列优化。
用二分队列优化的具体细节是这样的:
性质:从二分队列的队首转移是最优的,并且二分队列中元素的转移范围是递增的。
可以用二分队列优化的方程形如:
\(f[i] = \min f[j] + w(i, j)\),且方程满足决策单调性。
维护二分队列主要是弹出队首、弹出队尾和加入当前元素三部分。
首先,弹出转移范围不包括之后部分的元素。
然后,假设队尾的元素是 \(p\),它的转移范围是 \([l, r]\),当前位置是 \(i\)。如果用 \(i\) 转移 \(l\) 比用 \(p\) 转移 \(l\) 更优,因为一般情况下 \(i\) 的转移范围比 \(p\) 更靠后,所以此后的转移 \(i\) 一定优于 \(p\),故弹出 \(p\).
接下来考虑 \(i\) 的转移范围。因为方程满足决策单调性,所以可以用二分求出用 \(i\) 转移比用队首 \(h\) 转移更优的第一个位置 \(x\),那么 \(i\) 的转移范围是 \([x, n]\)
知道转移范围之后将 \(i\) 加入队尾即可。
注意二分的边界。
时间复杂度 \(O(T n \log n)\)
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 5;
const int maxl = 35;
int T, n, l, p;
int pre[maxn];
int dq[maxn], lft[maxn];
char s[maxn][maxl];
ld sum[maxn], f[maxn];
bool vis[maxn];
void init()
{
memset(pre, 0, sizeof(pre));
memset(vis, false, sizeof(vis));
}
ld qpow(ld base, int power)
{
ld res = 1;
while (power)
{
if (power & 1) res = res * base;
base = base * base;
power >>= 1;
}
return res;
}
ld calc(int lst, int cur) { return f[lst] + qpow(abs(sum[cur] - sum[lst] - l - 1), p); }
int query(int p, int q)
{
int L = max(p, q), R = n;
while (L < R)
{
int mid = (L + R) >> 1;
if (calc(p, mid) <= calc(q, mid)) R = mid;
else L = mid + 1;
}
if (R == n) return n + (calc(p, n) > calc(q, n));
return R;
}
int main()
{
// freopen("P1912_1.in", "r", stdin);
scanf("%d", &T);
while (T--)
{
init();
scanf("%d%d%d", &n, &l, &p);
for (int i = 1; i <= n; i++)
{
scanf("%s", s[i]);
sum[i] = sum[i - 1] + strlen(s[i]) + 1;
}
int h, t;
dq[h = t = 1] = 0;
for (int i = 1; i <= n; i++)
{
while ((h < t) && (lft[h + 1] <= i)) h++;
f[i] = calc(dq[h], i), pre[i] = dq[h];
while ((h < t) && (lft[t] >= query(i, dq[t]))) t--;
dq[++t] = i, lft[t] = query(i, dq[t - 1]);
// printf("debug %d\n", i);
// for (int j = h; j <= t; j++) printf("%d ", dq[j].p);
// putchar('\n');
}
if (f[n] > 1e18) puts("Too hard to arrange");
else
{
printf("%lld\n", (ll)f[n]);
for (int i = n; i; i = pre[i]) vis[i] = true;
int cur = 1;
while (cur <= n)
{
if (!vis[cur]) printf("%s ", s[cur]);
else printf("%s\n", s[cur]);
cur++;
}
}
puts("--------------------");
}
return 0;
}
标签:二分,ld,int,题解,P1912,转移,maxn,sum,NOI2009
From: https://www.cnblogs.com/lingspace/p/p1912.html