LuoguP5017 摆渡车 $dp$

题意

戳这里

吐槽

听同学说今年$pjT3$很难，于是就去看了下。

一眼斜率优化...为什么$n,m$这么小啊...

感觉这题出的还是不错的。

Solution

首先我们先转化一波题意：给出数轴上$n$个点，让你选择若干个两两距离大于等于$m$的点，使得每个点到右边第一个你选的点的距离和最小。

大力$dp$，发现可以斜率优化。

$pj$会考斜率优化？

冷静一波，显然每个点的决策肯定在$[i-m*2,i-m]$之间...

所以好像直接$O(max(t_i)*m)$转移常数小并不会$T$?

至少我$Luogu$数据过了...

#include<bits/stdc++.h>

#define For(i,x,y) for (register int i=(x);i<=(y);i++)

#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)

#define cross(i,u) for (register int i=first[u];i;i=last[i])

using namespace std;

typedef long long ll;

inline ll read(){

    ll x=0;int ch=getchar(),f=1;

    while (!isdigit(ch)&&(ch!='-')) ch=getchar();

    if (ch=='-'){f=-1;ch=getchar();}

    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

const int N = 1010, maxn = 5000110;

int n,m,Max,a[N],sum[maxn],Sum[maxn],dp[maxn];

bool vis[maxn];

inline void solve(){

	For(i,0,Max){

		dp[i]=Sum[i]*i-sum[i];

		For(j,max(0,i-2*m),i-m){

			int cnt=Sum[i]-Sum[j];

			dp[i]=min(dp[i],dp[j]+cnt*i-sum[i]+sum[j]);

		}

	}

	int ans=1e9;

	For(i,Max-m,Max) ans=min(ans,dp[i]);

	printf("%d",ans);

}

int main(){

	n=read(),m=read();

	For(i,1,n) a[i]=read(),Max=max(Max,a[i]),Sum[a[i]]++,sum[a[i]]+=a[i];

	Max+=m;

	For(i,1,Max) sum[i]+=sum[i-1],Sum[i]+=Sum[i-1];

	solve();

}

再冷静一波...好像有很多状态是没用的？

如果一个点前面的$m$个点中都没有给出的点那么$dp_i=dp_{i-m}$...

然后算下复杂度...好像是$O(nm+max(t_i))$

#include<bits/stdc++.h>

#define For(i,x,y) for (register int i=(x);i<=(y);i++)

#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)

#define cross(i,u) for (register int i=first[u];i;i=last[i])

using namespace std;

typedef long long ll;

inline ll read(){

    ll x=0;int ch=getchar(),f=1;

    while (!isdigit(ch)&&(ch!='-')) ch=getchar();

    if (ch=='-'){f=-1;ch=getchar();}

    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

const int N = 1010, maxn = 5000110;

int n,m,Max,a[N],sum[maxn],Sum[maxn],dp[maxn];

inline void solve(){

	For(i,0,Max){

		dp[i]=Sum[i]*i-sum[i];

		if (i>m&&Sum[i]-Sum[i-m]==0){dp[i]=dp[i-m];continue;}

		For(j,max(0,i-2*m),i-m){

			int cnt=Sum[i]-Sum[j];

			dp[i]=min(dp[i],dp[j]+cnt*i-sum[i]+sum[j]);

		}

	}

	int ans=1e9;

	For(i,Max-m,Max) ans=min(ans,dp[i]);

	printf("%d",ans);

}

int main(){

	n=read(),m=read();

	For(i,1,n) a[i]=read(),Max=max(Max,a[i]),Sum[a[i]]++,sum[a[i]]+=a[i];

	Max+=m;

	For(i,1,Max) sum[i]+=sum[i-1],Sum[i]+=Sum[i-1];

	solve();

}

口胡

不难发现最后有用的点数是$nm$...

我们把这$nm$个点抠出来，基排一下，然后直接斜率优化$dp$应该能做到优秀的$O(nm)$的复杂度。

给我把nm开到1000w，ti开到1e9

$upd:$我第二个复杂度好像算错了...应该是$O(nm^2+max(t_i))$

巴特西

LuoguP5017 摆渡车 $dp$

题意

吐槽

Solution

口胡

最新文章

热门文章