题解：P14424 [JOISC 2014] 邮戳收集 / Collecting Stamps

经过一个打卡点有四种方式：

$u+e$ 。
$d+v$ 。
$u+v$ 。
$e+d$ 。

考虑在东向电车行走的路线，可以跳过若干打卡点不走，其余走

u+v

，或者走

u+e

上去，把没走的打卡点挑若干个走

e+d

，挑一个走

d+v

下去。

注意

u+e

和

d+v

可能被走多次。

将

e+d

和

d+v

的贡献后置，在转移时加上额外贡献，令

f_{i,j,k}

表示到了站台

i

，有

j

个打卡点被指定走

d+e

，

k

个打卡点被指定走

d+v

，转移时加上

2T(j+k)

的贡献，枚举当前有

k_1

个

u+e

和前面匹配，

k_2

个

d+v

和后面匹配。可以做到

O(\text{poly}(n))

。

简化状态，由于在上面只能往左走，因此只有存在没有匹配的

d+v

时才能匹配存在未匹配的

d+e

，另一方面，我们做

u+e

和

d+v

的匹配时实际上顺便把

d+e

走了，可以把向上和向下理解称括号匹配，当存在未匹配的左括号时可以选择

d+e

。

令

dp_{i,j}

表示到了站台

i

，有

j

个未匹配的

d+v

的最小代价。

转移时，可以选择

u+v

，当

j>0

时可以选择

d+e

。枚举这个站台有

k1

个

u+e

和前面匹配，

k2

个

d+v

和后面匹配，转移到

dp_{i+1,j-k1}

或

dp_{i+1,j+k2}

。

前缀和优化可以做到

O(n^2)

。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,T;
int f[3005][3005];
int u[3005],v[3005],d[3005],e[3005];
void upd(int &x,int y){
	x=min(x,y);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>T;
	for(int i=1;i<=n;i++){
		cin>>u[i]>>v[i]>>d[i]>>e[i];
	}
	memset(f,0x3f,sizeof(f));
	f[1][0]=T+u[1]+v[1];
	for(int i=1;i<=n;i++){
		f[1][i]=T+(d[1]+v[1])*i;
	}
	f[1][1]=T+d[1]+v[1];
	e[n+1]=d[n+1]=0x3f3f3f3f; 
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			upd(f[i+1][j],f[i][j]+u[i+1]+v[i+1]+2*j*T+T);
			if(j>0) upd(f[i+1][j],f[i][j]+d[i+1]+e[i+1]+2*j*T+T);
		}
		int mn=f[i][0]+d[i+1]+v[i+1];
		for(int j=1;j<=n;j++){
			upd(f[i+1][j],mn+T);
			mn=min(mn,f[i][j]+2*j*T);
			mn+=d[i+1]+v[i+1];
		}
		mn=f[i][n]+e[i+1]+u[i+1]+2*n*T;
		for(int j=n-1;j>=0;j--){
			upd(f[i+1][j],mn+T);
			mn=min(mn,f[i][j]+2*j*T);
			mn+=e[i+1]+u[i+1];
		}
	}
	cout<<f[n+1][0]<<"\n";
}

题解：P14424 [JOISC 2014] 邮戳收集 / Collecting Stamps

文章操作

相关推荐

评论

题解：P14424 [JOISC 2014] 邮戳收集 / Collecting Stamps