CSP202209-5 高维亚空间超频物质变压缩技术

CSP202209-5高维亚空间超频物质变压缩技术

题意：

给定 $n$ 块黄金，每个黄金有体积 $v_i$ 。将黄金分组进行压缩，每一组内的黄金编号连续，压缩一组黄金的代价为 $s-L)^2$ ， $s$ 为改组黄金的体积和。

每块黄金有质量 $m_i$ ，分组必须满足组之间编号最大的的黄金质量递增。

询问分段压缩的最小代价。

解析：

子任务1，2

令 $f_i$ 为前 $i$ 块黄金都压缩完成的最小代价。

则 $f_i = \min\limits_{0<j<i}\Big\{ f_j + (s_i-s_j-L)^2\Big\}(m_i>m_j)$ ， $s$ 为 $v$ 的前缀和

初始条件 $f_0 = 0$ ，答案为 $f_n$ 。

此时时间时间复杂度为 $O(n^2)$

可以通过前两个测试点

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e6+10;
const int maxm = 1e5+10;
const double eps = 1e-12;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;
#define int llll n, L;
ll v[maxn], m[maxn], s[maxn];
ll f[maxn];signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> L;for(int i = 1; i <= n; i++){cin >> s[i];s[i] += s[i-1];}for(int i = 1; i <= n; i++)cin >> m[i];memset(f, INF, sizeof(f));f[0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j < i; j++){ //上一组的终点if(m[i] <= m[j])continue; f[i] = min(f[i], f[j]+(s[i]-s[j]-L) * (s[i]-s[j]-L));}}cout << f[n] << endl;return 0;}

子任务3

因为 $m_i = i$ ，所以对于 $i$ ，可以从任意 $j (j < i)$ 进行转移。

状态转移方程： $f_i = \min\limits_{0<j<i}\Big\{ f_j + (s_i-s_j-L)^2\Big\}$ 因为有 $s_i\times s_j$ 项，可以考虑斜率优化。

整理一下： $f_j+s_j^2+2Ls_j = 2s_i\times s_j+f_i-s_i^2+2Ls_i$ 确实是可以斜率优化的。 $y = f_j+s_j^2+2Ls_j, k = 2s_i, x = s_j$

而且 $k, x$ 都是单调的，所以可以用单调队列维护下凸壳。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e6+10;
const int maxm = 1e5+10;
const double eps = 1e-12;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;
#define int ll#define x(a) (s[a])
#define y(a) (f[a]+s[a]*s[a]+2*L*s[a]) 
#define k(a) (2*s[a])ll n, L;
ll v[maxn], m[maxn], s[maxn], p[maxn];
int q[maxn], hh = 1, tt = 0;
ll f[maxn];long double slope(int a, int b){long double x1 = (long double)x(a);long double y1 = (long double)y(a);long double x2 = (long double)x(b);long double y2 = (long double)y(b);if(fabs(x2-x1) < eps)return y2 > y1 ? 1e18 : -1e18;elsereturn (y2-y1)/(x2-x1);
}signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> L;for(int i = 1; i <= n; i++){cin >> s[i];s[i] += s[i-1];}for(int i = 1; i <= n; i++)cin >> m[i];if(n <= 2000){	memset(f, INF, sizeof(f));f[0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j < i; j++){if(m[i] <= m[j])continue; f[i] = min(f[i], f[j]+(s[i]-s[j]-L) * (s[i]-s[j]-L));}}cout << f[n] << endl;return 0;}else{q[++tt] = 0;f[0] = 0;	for(int i = 1; i <= n; i++){while(hh < tt && slope(q[hh], q[hh+1]) <= k(i))hh++;     int j = q[hh];f[i] = f[j] + (s[i]-s[j]-L) * (s[i]-s[j]-L);while(hh < tt && slope(q[tt-1], q[tt]) >= slope(q[tt], i))tt--;				q[++tt] = i;}	cout << f[n] << endl;return 0;}return 0;	
}

子任务4

$i$ 的决策点 $j$ 必须满足 $m_j < m_i$ ，增加一维偏序，可以CDQ分治。

根据黄金质量分为左右两部分。当左侧的状态值计算完成，用左侧的状态更新右侧的状态，必然满足质量的限制。

用左侧值更新右侧值时，左侧的 $x$ 单调，右侧处理成 $k$ 单调的情况，可以继续用单调队列维护下凸壳。

时间复杂度为 $O(n\log^2 n)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e6+10;
const int maxm = 1e5+10;
const double eps = 1e-12;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;
#define int ll#define x(a) (s[a])
#define y(a) (f[a]+s[a]*s[a]+2*L*s[a]) 
#define k(a) (2*s[a])ll n, L;
ll m[maxn], s[maxn];
int q[maxn], hh = 1, tt = 0;
ll f[maxn];
struct node{int m, id;ll k, x, y;
}a[maxn], tmp[maxn];
bool cmpm(node a, node b){if(a.m == b.m)return a.id < b.id;elsereturn a.m < b.m;
}
bool cmpx(node a, node b){return a.x < b.x;
}
long double slope(int i, int j){long double x1 = (long double)a[i].x;long double y1 = (long double)a[i].y;long double x2 = (long double)a[j].x;long double y2 = (long double)a[j].y;if(fabs(x2-x1) < eps)return y2 > y1 ? 1e18 : -1e18;elsereturn (y2-y1)/(x2-x1);
}void cdq(int ml, int mr, int pl, int pr){if(pl > pr)return;if(ml == mr){for(int i = pl; i <= pr; i++){int j = a[i].id;a[i].y = f[j] + s[j]*s[j] + 2 * L * s[j];}		return; }int mmid = (ml+mr) >> 1;int pmid = upper_bound(a+pl, a+1+pr, (node){mmid, n+1, 0, 0}, cmpm)-a-1;cdq(ml, mmid, pl, pmid);	int hh = 1, tt = 0;for(int i = pl; i <= pmid; i++){while(hh < tt && slope(q[tt-1], q[tt]) >= slope(q[tt], i))tt--;q[++tt] = i;}if(pr > pmid){sort(a+pmid+1, a+pr+1, cmpx);for(int i = pmid+1; i <= pr; i++){while(hh < tt && slope(q[hh], q[hh+1]) <= a[i].k)hh++;if(hh <= tt){int id = a[i].id;int j = a[q[hh]].id;if(id < j)continue;f[id] = min(f[id], f[j]+(s[id]-s[j]-L)*(s[id]-s[j]-L));}}sort(a+pmid+1, a+pr+1, cmpm);}cdq(mmid+1, mr, pmid+1, pr);	sort(a+pl, a+pr+1, cmpx);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> L;for(int i = 1; i <= n; i++){cin >> s[i];s[i] += s[i-1];}for(int i = 1; i <= n; i++)cin >> m[i];memset(f, INF, sizeof(f));f[1] = (s[1]-L) * (s[1]-L);for(int i = 1; i <= n; i++){a[i].id = i;a[i].m = m[i];a[i].k = 2 * s[i];a[i].x = s[i];f[i] = (s[i]-L) * (s[i]-L);}sort(a+1, a+1+n, cmpm); //按质量排序 cdq(1, n, 1, n);cout << f[n] << endl;return 0;}