网站导航
> 文章列表 > CSP202209-5 高维亚空间超频物质变压缩技术

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

网友: 文章列表 2024-03-21 23:43:03

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

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

题意：

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

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

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

解析：

子任务1，2

令 fif_ifi​ 为前 iii 块黄金都压缩完成的最小代价。

则 fi=min⁡0<j<i{fj+(si−sj−L)2}(mi>mj)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​)，sss 为 vvv 的前缀和

初始条件 f0=0f_0 = 0f0​=0，答案为 fnf_nfn​。

此时时间时间复杂度为 O(n2)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

因为 mi=im_i = imi​=i，所以对于 iii，可以从任意 j(j<i)j(j<i)j(j<i) 进行转移。

状态转移方程：fi=min⁡0<j<i{fj+(si−sj−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}因为有 si×sjs_i\\times s_jsi​×sj​ 项，可以考虑斜率优化。

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

而且 k,xk,xk,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

iii 的决策点 jjj 必须满足 mj<mim_j < m_imj​<mi​，增加一维偏序，可以CDQ分治。

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

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

时间复杂度为 O(nlog⁡2n)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;}
网络标签：

相关问题