首页 > 其他分享 >P5665 [CSP-S2019] 划分

P5665 [CSP-S2019] 划分

时间：2024-08-01 22:07:08浏览次数：16  
标签：typedef P5665 read ll long pair S2019 CSP define

思路：

首先求出 \(a\) 的前缀和数组 \(s\)。

考虑动态规划，令 \(dp_{i,j}\) 表示以 \(i\) 结尾，末尾有 \(j\) 个为一组的最小答案，则状态转移方程为：

\[dp_{i,j} = \min [s_{i-j}-s_{i-j-k} \le s_i - s_{i-j}] dp_{i-j,k} + (s_i - s_{i-j})^2 \]

朴素直接转移是 \(O(N^3)\) 的，可以得到 36pts 的好成绩代码就懒的给了。

考虑优化，对于求出最小的一个 \(k\)，使得 \(s_{i-j}-s_{i-j-k} > s_i - s_{i-j}\)，那么状态转移方程为：

\[dp_{i,j} = (s_i - s_{i-j})^2 + \min\limits_{l=1}^k dp_{i-j,l} \]

后面的一串可以提前前缀预处理好，现在的复杂度在求 \(k\) 上，注意到 \(s_{i,j} - s_{i-j-k}\) 是单调的，那么直接二分即可。

时间复杂度优化至 \(O(N^2 \log N)\)。

$O(N^2 \log N)$ 代码 
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=5050,INF=4e18;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
bool op;
ll n,l,r,h,t,ans=INF;
ll s[N],dp[N][N],f[N][N];
ll get(ll l,ll r){
	if(l>r)
	  return 0;
	if(!l)
	  return s[r];
	return s[r]-s[l-1];
}
bool End;
int main(){
	n=read(),op=read();
	for(int i=1;i<=n;i++)
	  s[i]=s[i-1]+read();
	dp[1][0]=f[1][0]=INF;
	dp[1][1]=f[1][1]=s[1]*s[1];
	for(int i=2;i<=n;i++){
		f[i][0]=dp[i][0]=INF;
		for(int j=1;j<=i;j++){
			l=1,r=i-j,t=0,h=get(i-j+1,i);
			if(s[i-j]<=h)
			  t=i-j+1;
			else{
				while(l<=r){
					ll mid=(l+r)>>1;
					if(get(i-j-mid+1,i-j)>h){
						t=mid;
						r=mid-1;
					}
					else
					  l=mid+1;
				}
			}
			dp[i][j]=f[i-j][t-1]+h*h;
			f[i][j]=min(f[i][j-1],dp[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	  ans=min(ans,dp[n][i]);
	write(ans);
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

之后我们可以发现，若 \(j\) 的单增的，则 \(i-j-k+1\) 是单降的，那么我们直接对 \(k\) 进行走指针即可，时间复杂度优化至 \(O(N^2)\)，可以拿到 64pts 的好成绩。

$O(N^2)$ 代码 
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=5050,INF=4e18;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
bool op;
ll n,t,h,sum,ans=INF;
ll s[N],a[N],dp[N][N],f[N][N];
ll get(ll l,ll r){
	if(l>r)
	  return 0;
	if(!l)
	  return s[r];
	return s[r]-s[l-1];
}
bool End;
int main(){
	n=read(),op=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		s[i]=s[i-1]+a[i];
	}
	dp[1][0]=f[1][0]=INF;
	dp[1][1]=f[1][1]=s[1]*s[1];
	for(int i=2;i<=n;i++){
		f[i][0]=dp[i][0]=INF;
		t=i-1,sum=a[i-1];
		for(int j=1;j<=i;j++){
			ll h=get(i-j+1,i);
			while(sum<=h&&t){
				t--;
				sum+=a[t];
			}
			dp[i][j]=f[i-j][i-j-t]+h*h;
			f[i][j]=min(f[i][j-1],dp[i][j]);
			sum-=a[i-j];
		}
	}
	for(int i=1;i<=n;i++)
	  ans=min(ans,dp[n][i]);
	write(ans);
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

因为我们这种 dp 的状态数都已经达到了 \(N^2\)，于是考虑找一些性质。

容易打表发现在合法情况下，满足 \(dp_{i,j} \le dp_{i,j+1}\)。

那么我们可以找到每个位置 \(i\)，记录一下 \(f_i\) 表示 \(\min dp_{i,j}\)，且最后一段为 \([g_i,i]\)，则状态转移方程为：

\[f_i = \min\limits_{j=0}^{i-1} [s_j-s_{g_j-1} \le s_i - s_j] f_j + (s_i - s_j)^2 \]

此时我们就将状态时将至 \(O(N)\) 级别，现在考虑来优化状态转移方程。

$O(N)$ 状态代码 
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=5e5+10,INF=4e18;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
bool op;
ll n,t,h,ans=INF;
ll s[N],a[N],f[N],g[N];
ll get(ll l,ll r){
	if(l>r)
	  return 0;
	if(l<0)
	  return s[r];
	return s[r]-s[l-1];
}
bool End;
int main(){
	n=read(),op=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		s[i]=s[i-1]+a[i];
		f[i]=INF;
	}
	g[1]=1;
	f[0]=g[0]=0;
	f[1]=s[1]*s[1];
	for(int i=2;i<=n;i++){
		for(int j=0;j<i;j++){
			h=get(g[j],j),t=get(j+1,i);
			if(h>t)
			  continue;
			if(f[j]+t*t<f[i]){
				f[i]=f[j]+t*t;
				g[i]=j+1;
			}
		}
	}
	write(f[n]);
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

容易发现，当 \(j\) 最大时，这个式子的值最小，所以我们需要求出一个最大的 \(j\) 满足 \(s_j-s_{g_j-1} \le s_i - s_j\)，即：

\[2s_j - s_{g_j-1} \le s_i \]

注意到 \(s_i\) 单增，我们可以维护一个 \(2s_j - s_{g_j-1}\) 单增的单调队列，然后找到这个队列最后一个满足条件的 \(j\)，那么 \(j\) 以前的数对答案无法造成贡献，将其弹出。

这样每个数至多被弹出一次，时间复杂度为 \(O(N)\)。

完整代码：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
typedef __int128 __;
bool Begin;
const ll N=4e7+5,mod=1ll<<30;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(__ x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
__ t,ans;
bool op;
int n,head=1,tail=0;
ll s[N],g[N];
int Q[N];
inline void Read(){
	ll x,y,z,m,p,l,r,pre=0;
	x=read(),y=read(),z=read(),s[1]=read(),s[2]=read(),m=read();
	for(int i=3;i<=n;i++)
	  s[i]=(x*s[i-1]+y*s[i-2]+z)%mod;
	for(int i=1;i<=m;i++){
		p=read(),l=read(),r=read();
		for(int j=pre+1;j<=p;j++)
		  s[j]=(s[j]%(r-l+1))+l;
		pre=p;
	}
}
inline ll get(int l,int r){
	if(l>r)
	  return 0;
	if(l<1)
	  return s[r];
	return s[r]-s[l-1];
}
inline ll date(ll x){
	return 2ll*s[x]-s[g[x]-1];
}
bool End;
int main(){
	n=read(),op=read();
	if(op==1)
	  Read();
	else{
		for(int i=1;i<=n;i++)
		  s[i]=read();
	}
	for(int i=1;i<=n;i++)
	  s[i]+=s[i-1];
	g[1]=1,g[0]=0;
	Q[++tail]=0,Q[++tail]=1;
	for(int i=2;i<=n;i++){
		while(date(Q[head+1])<=s[i]&&head+1<=tail)
		  head++;
		g[i]=Q[head]+1;
		t=get(g[i],i);
		while(date(i)<=date(Q[tail])&&tail>=head)
		  tail--;
		Q[++tail]=i;
	}
	for(int i=n;i>=1;i=g[i]-1)
	  ans+=(__)(s[i]-s[g[i]-1])*(s[i]-s[g[i]-1]);
	write(ans);
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}

标签：typedef,P5665,read,ll,long,pair,S2019,CSP,define
From： https://www.cnblogs.com/rgw2010/p/18336475

相关文章

  • 『模拟赛』暑假集训CSP提高模拟13
    Rank上半最后一次正式模拟赛，感觉还彳亍A.小孩召开法1原[ABC278F]Shiritori签到题。博弈论+状压+记搜秒了，感觉不用太细说。不过是暑假以来第一次首A啊，开始还胡乱想SG定理的做法，后来发现不用那么复杂。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for......
  • 暑假集训CSP提高模拟13
    暑假集训CSP提高模拟13暑假集训CSP提高模拟13组题人：@joke3579\(T1\)P185.小孩召开法1\(43pts\)原题：[ABC278F]Shiritori部分分未知\(pts\)：乱搞。正解状压加记忆化搜索。记录所选字符串的状态及上一个选择的字符串。当存在对方必败时自己必胜。点击......
  • 暑假集训csp提高模拟13
    赛时rank28,T144,T20,T330,T45啊哈哈哈哈哈，我要挂没啦，啊哈哈哈哈哈哈哈哈哈最后10min的心路历程感觉应该又要挂分了(11:20)感觉一分没有(11:23)要被薄纱了(11:25)感觉人均AK，就我不会(11:25)啊哈哈哈哈哈，我太菜了，我要AF0了(11:27)啊哈哈哈，看了一眼自己代码，我咋只......
  • [赛记] 暑假集训CSP提高模拟 #N/A 总结
    没写的有些多，所以一块写EVA原题：忘了；贪心；赛时将每条鱼放在了右端点，导致分的情况太多，最后没打完；贪心的想一下，将每条鱼放在网的左或右端点肯定不会更劣；将每条鱼作为网的左端点，然后利用相对运动的知识统计出剩下$n-1$条鱼的进入和出去网的范围的时间（可以将出去的时间稍......
  • CSP-J2019公交换乘
    马上CSP2024了，做题ing...(题目描述戳它思路1.用结构体双端队列存票，用双端队列的原因是后面要遍历2.结构体元素：price+time+used3.过期的票要及时pop4.不要一边遍历一边pop,用used标记代码#include<bits/stdc++.h>usingnamespacestd;structTicket{intprice......
  • 暑假集训CSP提高模拟12
    T1这题千万不要认为是莫反题枚举质因子\(x,y\)，\(x,y<=998\),对答案的贡献为\(min(\lfloor{\frac{B}{x}}\rfloor,\lfloor{\frac{D}{y}}\rfloor)\)，再容斥一下即可MD最后答案要取模啊点击查看代码#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.t......
  • 『模拟赛』暑假集训CSP提高模拟12
    Rank正常偏下发挥吧。A.黑客签到题。题目中的关键点是只有\(x\)和\(y\)的和在区间\(\left[0,999\right]\)内才合法，因此我们只枚举和在这个范围内的两个值，寻找约分前的值即可，复杂度为\(\mathcal{O(999^2)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,......
  • 暑假集训CSP提高模拟12
    暑假集训CSP提高模拟12\(T1\)P171.黑客\(40pts\)将式子进行二维差分。考虑枚举\(\frac{i+j}{\gcd(i,j)}=t\)，并统计它能对答案产生的贡献。令\(\gcd(i,j)=1\)，这样的话才会不重不漏。推式子，有\(\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\fr......
  • 暑假集训CSP提高模拟 ∫[0,6] (x^2)/6 dx
    \[\text{暑假集训CSP提高模拟}\int^{6}_{0}\frac{x^{2}}{6}dx\]A.黑客显然这个题里只有\(999\)放在复杂度里是有可能对的，要么是\(999^{2}\)要么是\(999^{2}\log999\)，显然应该是前者.考虑枚举全部的最简分数，然后乘上去，算的时候直接算当前分母/分子是最简分式的几倍（注意上......
  • 暑假集训csp提高模拟12
    赛时rank47，T1100,T20,T30,T420做题策略不好，没做T2，死在T4上了。感觉赛时就是唐。T1黑客考虑枚举结果，如果存在贡献，那么一定有\(i+j=k\&gcd(i,j)=1\)，统计一下有多少组即可点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//usingnamespace__gnu_pbds;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99