JOISC2014 スタンプラリー

题目:

  IOI 铁路是由 个站点构成的直线线路。这条线路的车站从某一端的车站开始顺次标号为
  这条路线上行驶的电车分为上行电车和下行电车两种,上行电车沿编号增大方向行驶,下行电车沿编号减小方向行驶。乘坐这两种电车的话,移动 站的距离需要 秒。换句话说,乘坐上行电车从车站 走到车站 需要 秒,乘坐下行电车从车站 走到车站 也需要 秒。你不能在 号车站乘坐下行电车,或在 号车站乘坐上行电车。由于电车发车的频率非常高,你可以无视等待电车消耗的时间。
  每个车站设有上行电车的站台和下行电车的站台,连接两个站台的道路上设有邮戳台。
  现在,IOI 铁路召开了邮戳拉力赛。在拉力赛中,选手需要从 号车站的上行电车站台出发,在 号车站各盖一枚邮戳,最终到达 号车站的上行电车站台即可完成。
  为了在每个车站盖上邮戳,必须从电车上下来,步行走到车站通路上的邮戳台。在 号车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间如下所示:

  • 从车站 的上行电车站台到邮戳台的时间为 秒;
  • 从车站 的邮戳台到上行电车站台的时间为 秒;
  • 从车站 的下行电车站台到邮戳台的时间为 秒;
  • 从车站 的邮戳台到下行电车站台的时间为 秒;

  邮戳拉力赛的选手在 号车站与 号车站都只能停留一次。 号车站都可以访问任意多次。
  
  现在给出有邮戳台的车站个数、乘坐电车移动一站的时间、在每个车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间,请你求出完成邮戳拉力赛的最短时间。 这个时间包括从 号车站出发,按下 个邮戳后到达 号车站的时间。无视等车的时间和按邮戳的时间。

思路:

  因为 ,显然不能状压保存每个邮戳是否得到。所以要用另一种方法保证每个邮戳都被取到。
  既然不能保存邮戳是否被取到,那就单独考虑每个邮戳被取到的方案。对于每个邮戳有 种方法去取它:
  
  但是这样任意组成的路径不一定可行,所以考虑如何保证路径是合法的。因为起点和终点都在左边,所以可以把往左走的操作()看做'(',把往右走的操作()看做')'。如果最后得到的序列是一个合法的括号序列就代表路径合法。
  那么前面提到的 种取邮戳的方法就可以转化为:(因为左边是往上的,所以前后括号和走的顺序是相反的,手动模拟理解)。设 表示到第 个邮戳,未匹配的左括号还有 个的最短时间。因为每两个左括号就代表后面还要到下行电车一次,所以 在更新 时都要加上

代码:

#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int N=3010;

ll dp[2][N];

int main(){
    int n,t;
    scanf("%d%d",&n,&t);
    mset(dp[0],63);dp[0][0]=0;
    rep(i,1,n){
        int u,v,d,e;
        scanf("%d%d%d%d",&u,&v,&d,&e);
        mset(dp[i&1],63);
        rep(j,0,n)dp[i-1&1][j]+=j*2*t+t;
        rep(j,0,n)tomin(dp[i&1][j],dp[i-1&1][j]+u+v);// ()
        rep(j,1,n)tomin(dp[i&1][j],dp[i-1&1][j]+d+e);// )(
        rep(j,1,n)tomin(dp[i&1][j],std::min(dp[i-1&1][j-1],dp[i&1][j-1])+v+d);// ((
        drep(j,n,0)tomin(dp[i&1][j],std::min(dp[i-1&1][j+1],dp[i&1][j+1])+u+e);// ))
    }
    printf("%lld\n",dp[n&1][0]+t);
    return 0;
}