CSP202209

CSP202209

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

题意：

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

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

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

解析：

子任务1，2

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

则 f i = min ⁡ 0 < j < i { f j + ( s i − s j − L ) 2 } ( m i > m j ) f_i = \min\limits_{0<j<i}\Big\{ f_j + (s_i-s_j-L)^2\Big\}(m_i>m_j) fi​=0<j<imin​{fj​+(si​−sj​−L)2}(mi​>mj​)， s s s 为 v v v 的前缀和

初始条件 f 0 = 0 f_0 = 0 f0​=0，答案为 f n f_n fn​。

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

可以通过前两个测试点

代码如下：

#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 m_i = i mi​=i，所以对于 i i i，可以从任意 j ( j < i ) j(j<i) j(j<i) 进行转移。

状态转移方程： f i = min ⁡ 0 < j < i { f j + ( s i − s j − L ) 2 } f_i = \min\limits_{0<j<i}\Big\{ f_j + (s_i-s_j-L)^2\Big\} fi​=0<j<imin​{fj​+(si​−sj​−L)2}因为有 s i × s j s_i\times s_j si​×sj​ 项，可以考虑斜率优化。

整理一下： f j + s j 2 + 2 L s j = 2 s i × s j + f i − s i 2 + 2 L s i f_j+s_j^2+2Ls_j = 2s_i\times s_j+f_i-s_i^2+2Ls_i fj​+sj2​+2Lsj​=2si​×sj​+fi​−si2​+2Lsi​确实是可以斜率优化的。 y = f j + s j 2 + 2 L s j , k = 2 s i , x = s j y = f_j+s_j^2+2Ls_j, k = 2s_i, x = s_j y=fj​+sj2​+2Lsj​,k=2si​,x=sj​

而且 k , x k,x 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 i i 的决策点 j j j 必须满足 m j < m i m_j < m_i mj​<mi​，增加一维偏序，可以CDQ分治。

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

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

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

代码：

#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;}