JOISC 2014 邮戳拉力赛（基础DP）

题意

https://loj.ac/problem/2878

思路

真的神仙题，想到就很好写，想不到就写不出来。

肯定只能一个一个邮戳按顺序分析。首先，将取一枚邮戳的路径分为四种：

• 上行 \(\rightarrow\) 邮戳台 \(\rightarrow\) 上行 简称路径 \((U,V)\)
• 上行 \(\rightarrow\) 邮戳台 \(\rightarrow\) 下行 简称路径 \((U,E)\)
• 下行 \(\rightarrow\) 邮戳台 \(\rightarrow\) 下行 简称路径 \((D,E)\)
• 下行 \(\rightarrow\) 邮戳台 \(\rightarrow\) 上行 简称路径 \((D,V)\)

取一枚邮戳也就这四种路径。

但我们发现，路径 \((D,V)\) 的出现前提是有路径 \((U,E)\) 在前面出现过，也就是说到任意一个点路径 \((U,E)\) 的条数总是多余路径 \((D,V)\) 。也是说，我们可以将 \((U,E)\) 的条数减 \((D,V)\) 的条数当 \(\text{dp}\) 的第二维，也就是还未抵消的 \((U,E)\) 路径。另外 \((D,V)\) 路径出现的条件为至少有一个还未抵消的 \((U,E)\) 路径。

那么转移就是上述的四种，一个 \(O(n^3)\) 的暴力很快就能出来了

chk_min(dp[i][j],dp[i-1][j]+u+v);

if(j>0)chk_min(dp[i][j],dp[i-1][j]+d+e);

FOR(k,1,j)chk_min(dp[i][j],dp[i-1][j-k]+(d+v)*k);

FOR(k,1,n-j)chk_min(dp[i][j],dp[i-1][j+k]+(u+e)*k);

dp[i][j]+=(ll)T*(2*j+1);	//计算j个(D,V)路径的贡献

不难发现后面两维可以直接前后缀优化，或者背包转移，复杂度就优化至 \(O(n^2)\) 了。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

using namespace std;

template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}

template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}

typedef long long ll;

const int N=3005;

ll dp[N][N],f[N],g[N];

int n,T;

int main()

{

	scanf("%d%d",&n,&T);

	memset(dp,0x3f,sizeof(dp));

	dp[0][0]=0;

	FOR(i,1,n)

	{

		int u,v,d,e;

		scanf("%d%d%d%d",&u,&v,&d,&e);

		FOR(j,0,n)f[j]=g[j]=dp[i-1][j];

		FOR(j,1,n)chk_min(f[j],f[j-1]+(d+v));

		DOR(j,n-1,0)chk_min(g[j],g[j+1]+(u+e));

		FOR(j,0,n)

		{

			chk_min(dp[i][j],dp[i-1][j]+u+v);

			if(j>0)chk_min(dp[i][j],dp[i-1][j]+d+e);

//			FOR(k,1,j)chk_min(dp[i][j],dp[i-1][j-k]+(d+v)*k);

//			FOR(k,1,n-j)chk_min(dp[i][j],dp[i-1][j+k]+(u+e)*k);

			if(j>0)chk_min(dp[i][j],f[j-1]+(d+v));

			if(j<n)chk_min(dp[i][j],g[j+1]+(u+e));

			dp[i][j]+=(ll)T*(2*j);

		}

	}

	printf("%lld\n",dp[n][0]+(n+1)*T);

	return 0;

}