正题

题目链接:https://www.luogu.com.cn/problem/CF573D

题目大意

给出\(n\)个人\(n\)匹马，每个人/马有能力值\(w_i\)/\(h_i\)。

第\(i\)个人开始对应第\(i\)匹马，每个人不能选择对应的马，给每个人分配一个马后求最大的\(\sum w_i\times h_j\)。

每次交换两个人对应的马后求答案。

\(1\leq n\leq 30000,1\leq q\leq 10000\)

解题思路

设\(f_i\)表示匹配完前\(i\)匹马时的最大价值和。

考虑怎么转移，因为人和马一一对应，正常来说大的对大的乘积的和最大。但是如果恰好第\(i\)个人对应了第\(i\)匹马，那么显然\(i\)只能选择\(i+1\)，而让\(i+1\)选择\(i\)。

然后还有一种情况是只有三个时，第一个人对应了第一匹马，上面的转移会使得最后一个人和最后一匹马无法匹配，故我们还需要考虑和第三个的匹配。

也就是\(f_i\)只会从\(f_{i-1},f_{i-2},f_{i-3}\)转移过来，所以上动态\(dp\)即可

时间复杂度\(O(3^3n\log n )\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=31000,inf=1e18,S=3;

struct matrix{

	ll a[S][S];

}w[N<<4],c,tt;

struct node{

	ll p,w;

}e[N],h[N];

ll n,m,id[N];

matrix operator*(const matrix &a,const matrix &b){

	memset(c.a,0xcf,sizeof(c.a));

	for(ll i=0;i<S;i++)

		for(ll j=0;j<S;j++)

			for(ll k=0;k<S;k++)

				c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);

	return c;

}

bool cmp(node x,node y){return x.w>y.w;}

void Change(ll x,ll L,ll R,ll pos,matrix &val){

	if(L==R){w[x]=val;return;}

	ll mid=(L+R)>>1;

	if(pos<=mid)Change(x*2,L,mid,pos,val);

	else Change(x*2+1,mid+1,R,pos,val);

	w[x]=w[x*2]*w[x*2+1];

}

ll calc(ll l,ll r){

	if(l<=0)return -inf;

	ll n=r-l+1,c[4]={0,1,2,0},ans=-inf;

	do{

		ll sum=0;

		for(ll j=0;j<n;j++){

			if(e[l+c[j]].p==h[l+j].p){sum=-inf;break;}

			sum=sum+e[l+c[j]].w*h[l+j].w;

		}

		ans=max(ans,sum);

	}while(next_permutation(c,c+n));

	return ans;

}

void Updata(ll x){

	if(x>n)return;

	memset(tt.a,0xcf,sizeof(tt.a));

	tt.a[1][0]=0;tt.a[2][1]=0;

	tt.a[0][2]=calc(x-2,x);

	tt.a[1][2]=calc(x-1,x);

	tt.a[2][2]=calc(x,x);

	Change(1,1,n,x,tt);return;

}

signed main()

{

	scanf("%lld%lld",&n,&m);

//	memset(tt.a,0xcf,sizeof(tt.a));

//	tt.a[0][0]=tt.a[1][1]=tt.a[2][2]=0;

//	for(ll i=1;i<(N<<2);i++)w[i]=tt[i];

	for(ll i=1;i<=n;i++)scanf("%lld",&e[i].w),e[i].p=i;

	for(ll i=1;i<=n;i++)scanf("%lld",&h[i].w),h[i].p=i;

	sort(e+1,e+1+n,cmp);

	sort(h+1,h+1+n,cmp);

	for(ll i=1;i<=n;i++)id[e[i].p]=i;

	for(ll i=1;i<=n;i++)Updata(i);

	while(m--){

		ll l,r;

		scanf("%lld%lld",&l,&r);

		l=id[l];r=id[r];

		swap(e[l].p,e[r].p);

		for(ll i=0;i<3;i++)

			Updata(l+i),Updata(r+i);

		printf("%lld\n",w[1].a[2][2]);

	}

	return 0;

}

巴特西

CF573D-Bear and Cavalry【动态dp】

正题

题目大意

解题思路

code

最新文章

热门文章