求助四边形不等式dp
查看原帖
求助四边形不等式dp
332914
happybob楼主2022/7/26 16:48
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;

#define int long long

const int N = 3e6 + 5;

#define LD long double

int n, l, p, tf;
char s[N][31];
LD f[N];
int sum[N];

LD val(int x, int y)
{
	LD res = 1;
	LD b = abs(sum[y] - sum[x] + y - x - 1 - l);
	for (int i = 1; i <= p; i++) res *= b;
	return res + f[x];
}

struct Node
{
	int c, l, r;
}q[N];

int h, t, op[N];

void insert(int x)
{
	int pos = n + 1;
	while (h <= t && val(q[t].c, q[t].l) >= val(x, q[t].l)) pos = q[t--].l;
	if (h <= t && val(q[t].c, q[t].r) >= val(x, q[t].r))
	{
		int l = q[t].l, r = q[t].r;
		while (l + 1 < r)
		{
			int mid = (l + r) >> 1;
			if (val(q[t].c, mid) >= val(x, mid)) r = mid;
			else l = mid;
		}
		q[t].r = r - 1;
		pos = r;
	}
	if (pos != n + 1)
	{
		q[++t] = { x, pos, n };
	}
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> tf;
	while (tf--)
	{
		cin >> n >> l >> p;
		for (int i = n; i >= 1; i--) cin >> s[i];
		for (int i = 1; i <= n; i++)
		{
			f[i] = 0;
			sum[i] = sum[i - 1] + strlen(s[i]);
		}
		h = t = 0;
		q[0] = { 0, 1, n };
		for (int i = 1; i <= n; i++)
		{
			f[i] = val(q[h].c, i);
			op[i] = q[h].c;
			if (q[h].r == i) h++;
			q[h].l = i + 1;
			insert(i);
		}
		if (f[n] > 1e18) cout << "Too hard to arrange\n";
		else
		{
			cout << (int)f[n] << "\n";
			for (int i = n; i; i = op[i])
			{
				for (int j = i; j > op[i]; j--)
				{
					cout << s[j];
					if (j != op[i] + 1) cout << " ";
				}
				cout << "\n";
			}
			cout << "--------------------\n";
		}
	}
	return 0;
}

rt,spj返回 layout is wrong,这个意味着什么

2022/7/26 16:48
加载中...