UVA1336 - Fixing the Great Wall （区间DP）

小鱼儿 2021-12-14 22:31 207阅读 0赞

## 题意：用机器人修复分布在一条直线段上的n个损坏点，对于每个点i，x\[i\]表示位置，c\[i\]为立刻修缮的费用，d\[i\]为单位时间增加的维修费用。例如若在时刻t修缮i号点，则费用为ci+t∗di。给出机器人的初始位置x，速度v。求出修缮所有点的最小费用。 ##

## 分析：在任意时刻，机器人修完的点肯定是一个连续的区间，这个区间的费用不会再增加，它接下来每移动一步，增加的费用都等于区间外的d之和乘以时间。f\[i\]\[j\]\[k\]为修复完i~j，当前位置在k（k为0则在x\[i\]，为1则在x\[j\]）之后所有的费用。可以用Color Length这道题的思路，即转移时每走一单位时间，就把这一单位时间中为修缮的点所产生的费用全部累加起来。（f\[i\]\[j\]\[0/1\]表示i到j这一段已经修完了，且机器人在左/右端，最小化费是多少，然后转移就行了 ） ##

## 参考：[https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/82117270][https_blog.csdn.net_FSAHFGSADHSAKNDAS_article_details_82117270]。 ##

## 代码： ##

#include <bits/stdc++.h>
    #define maxn 1010
    #define ll long long
    #define linf (1ll<<60)
    using namespace std;
    struct point
    {
        ll x, c, d;
    } pt[maxn];
    ll N, V, x0, ans, f[maxn][maxn][2], s[maxn];
    bool operator<(point p1, point p2)
    {
        return p1.x<p2.x;
    }
    void init()
    {
        ll i;
        for(i=1; i<=N; i++)scanf("%lld%lld%lld",&pt[i].x,&pt[i].c,&pt[i].d);
        N++;
        pt[N].x=x0, pt[N].c=0, pt[N].d=0;
        sort(pt+1,pt+N+1);
        for(i=1; i<=N; i++)s[i]=s[i-1]+pt[i].d;
    }
    void work()
    {
        ll i, j, l, ans;
        for(i=1; i<=N; i++)
            for(j=i; j<=N; j++)
                if(i==j and pt[i].x==x0)f[i][j][0]=f[i][j][1]=0;///发酵点
                else f[i][j][0]=f[i][j][1]=linf;
        for(l=2; l<=N; l++) ///枚举区间长度
            for(i=1; i+l-1<=N; i++)
            {
                j=i+l-1;
                f[i][j][0]=min(f[i+1][j][0]+(pt[i+1].x-pt[i].x)*(s[N]-(s[j]-s[i])),f[i+1][j][1]+(pt[j].x-pt[i].x)*(s[N]-(s[j]-s[i])));
                f[i][j][1]=min(f[i][j-1][0]+(pt[j].x-pt[i].x)*(s[N]-(s[j-1]-s[i-1])),f[i][j-1][1]+(pt[j].x-pt[j-1].x)*(s[N]-(s[j-1]-s[i-1])));
            }
        ans=min(f[1][N][0],f[1][N][1])/V;///速度延后除 简洁代码
        for(i=1; i<=N; i++)ans+=pt[i].c;///费用延后加
        printf("%lld\n",ans);
    }
    int main()
    {
        while((~scanf("%lld%lld%lld",&N,&V,&x0)) and (N+V+x0))init(), work();
        return 0;
    }

## LRJ代码（记忆化搜索）： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1000 + 5;
    const double INF = 1e30;
    struct Section {
      double x, c, dt;
      bool operator < (const Section& rhs) const {
        return x < rhs.x;
      }
    } s[maxn];
    
    int kase, n;
    int vis[maxn][maxn][2];
    double v, x, d[maxn][maxn][2];
    double psdt[maxn]; // prefix sum of dt
    // cost accumulated when walking from x1 and x2.
    // section[i~j] are already finished
    double cost(double x1, double x2, int i, int j) {
      double finished_dt = 0;
      assert(i <= j);
      if(i >= 0 && j >= 0) finished_dt += psdt[j] - psdt[i-1];
      return (psdt[n] - finished_dt) * fabs(x2 - x1) / v;
    }
    
    double dp(int i, int j, int p) {
      if(i == 1 && j == n) return 0;
      double& ans = d[i][j][p];
      if(vis[i][j][p] == kase) return ans;
      vis[i][j][p] = kase;
      ans = INF;
      double x = (p == 0 ? s[i].x : s[j].x);
      if(i > 1) ans = min(ans, dp(i-1, j, 0) + cost(x, s[i-1].x, i, j));
      if(j < n) ans = min(ans, dp(i, j+1, 1) + cost(x, s[j+1].x, i, j));
      return ans;
    }
    
    int main() {
      memset(vis, 0, sizeof(vis));
      while(scanf("%d%lf%lf", &n, &v, &x) == 3 && n) {
        ++kase;
        double sumc = 0;
        for(int i = 1; i <= n; i++) {
          scanf("%lf%lf%lf", &s[i].x, &s[i].c, &s[i].dt);
          sumc += s[i].c;
        }
        sort(s+1, s+n+1); // in increasing order of position
        psdt[0] = 0;
        for(int i = 1; i <= n; i++)
          psdt[i] = psdt[i-1] + s[i].dt;
        s[0].x = -INF;
        s[n+1].x = INF;
        double ans = INF;
        for(int i = 1; i <= n+1; i++)
          if(x > s[i-1].x && x < s[i].x) {
            if(i > 1) ans = min(ans, dp(i-1, i-1, 0) + cost(x, s[i-1].x, -1, -1)); // move left
            if(i <= n) ans = min(ans, dp(i, i, 0) + cost(x, s[i].x, -1, -1)); // move right
            break;
          }
        printf("%.0lf\n", floor(ans + sumc));
      }
      return 0;
    }

[https_blog.csdn.net_FSAHFGSADHSAKNDAS_article_details_82117270]: https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/82117270