BZOJ 4244 邮戳拉力赛 (DP)

手动博客搬家: 本文发表于20181211 18:01:21, 原地址https://blog.csdn.net/suncongbo/article/details/84957907

为了防止我的博客被数学占领(一半以上的博文和数学相关)，我决定添加几道非数学题的题解。

目前数学题比例: $\frac{15}{32}=0.46875$

扯淡结束

题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=4244

题意: 太长了自己看。

题解:

额……这个题初一的时候好像就在模拟赛里见过。(ckw巨佬当场切掉)

考虑dp: 设$dp[i][j]$表示考虑前$i$个位置，其中有$j$趟车开往$i$右边的位置(不包括$i$)的最小代价。

胡乱转移即可。

……等等……这个题解是不是不太详细……

详细解释一下。

$A[i]$ 从左边进入$i$的费用。

$B[i]$ 从$i$到右边的费用。

$C[i]$ 从右边进入$i$的费用。

$D[i]$ 从$i$到左边的费用。

则从$j$到$i$的费用是$$w(i,j)=T(i-j)+B[j]+A[i] (j<i)$$$$w(i,j)=T(j-i)+D[j]+Ci$$

然后我们拆一拆式子，以$j<i$为例:

$w(i,j)=(Ti+A[i])+(-Tj+B[j])$

然后我们发现一个了不起的性质——贡献的式子对于$i,j$是独立的，对于同一个$i$来说，$j$是多少对贡献并没有影响，有影响的只是$j$和$i$的大小关系！

于是我们设计出前面所述的状态

转移比较麻烦，我们先考虑一个简化版问题：如果每个点只能经过一次？

考虑枚举当前点的$4$种进出状态

左进左出，这样相当于一个原来到右边$i$的现在变成了左边,因此右边的数量$-1$. 从$dp[i-1][j+1]$转移来
左进右出，从$dp[i-1][j]$转移来
右进左出，从$dp[i-1][j]$转移来
右进右出，从$dp[i-1][j-1]$转移来

注意(3)(4)两种情况要特判$j>0$（想一想为什么）

那如果可以经过多次？加一个类似于完全背包的转移，详见代码。

（继续瞎扯）我做这题的时候，写完了狂WA不止，然后上网搜题解，发现全是什么括号序列，蒙蔽了。

刚准备抄标程的时候，我发现标程除了方程完全不一样，还比我多个特判。

然后我把我的方程加了这个特判。切了……

好了，那么标程是怎么写的呢？

思路是，考虑把原序列转化成括号序列。

左进左出为右括号，右进右出为左括号，然后设了一个和我差不多的dp状态。

然而转移大不相同。因为这种计算方法是答案等于所有匹配的括号的距离之和，计算每一个位置对答案的贡献就是跨过该位置的括号对个数。

总结：用括号序列表示问题是一种不错的思路。

代码实现

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define llong long long

using namespace std;

const int N = 3000;

llong a[N+3];

llong b[N+3];

llong c[N+3];

llong d[N+3];

llong dp[N+3][N+3];

int n; llong t;

int main()

{

    scanf("%d%lld",&n,&t);

    for(int i=1; i<=n; i++) scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]);

    memset(dp,42,sizeof(dp));

    dp[0][0] = 0ll;

    for(int i=1; i<=n; i++)

    {

        for(int j=0; j<=n; j++)

        {

         if(j)

         {

          dp[i][j] = min(dp[i][j],dp[i-1][j-1]+(-t*i+c[i])+(-t*i+b[i]));

          dp[i][j] = min(dp[i][j],dp[i-1][j]+(-t*i+c[i])+(t*i+d[i]));

         }

            dp[i][j] = min(dp[i][j],dp[i-1][j]+(t*i+a[i])+(-t*i+b[i]));

            dp[i][j] = min(dp[i][j],dp[i-1][j+1]+(t*i+d[i])+(t*i+a[i]));

        }

        for(int j=1; j<=n; j++) dp[i][j] = min(dp[i][j],dp[i][j-1]+(-t*i+c[i])+(-t*i+b[i]));

        for(int j=n-1; j>=0; j--) dp[i][j] = min(dp[i][j],dp[i][j+1]+(t*i+a[i])+(t*i+d[i]));

    }

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

    return 0;

}

巴特西

BZOJ 4244 邮戳拉力赛 (DP)

最新文章

热门文章