UVA-1336 Fixing the Great Wall（区间DP）

题目大意：长城（视作x正半轴）有n处破损。有一个智能修复机器人，它的初始位置和移动速度已知。每处破损处都有一组参数(x,c,d)，x表示位置，c、d表示在时间t后再修复该处破损的花费为d*t+c。求用一个机器人修复所有破损的最小花费。

题目分析：要想最终代价最低，就不能跳跃着修复，也就是经过一段时间后已经修复好的破损应是一段连续区间。定义dp(i,j,k)表示修好(i,j)后机器人停留在k（0表示在左端，1表示在右端）端的费用。修复某处破损的代价虽然不是定值，但却是随着时间线性增长的，所以当修复完一处或一段破损时，修复其他破损的费用可以算出来，只需将其累加到当前状态即可，也可以视作修复某处破损产生的时间代价。状态转移方程：dp(i,j,1)=min(dp(i,j-1,0)+w1,dp(i,j-1,1)+w2)　　dp(i,j,0)=min(dp(i+1,j,0)+w3,dp(i+1,j,1)+w4) 其中，w1、w2、w3、w4为相应产生的时间代价与修复代价的和。

代码如下：

# include<iostream>

# include<cstdio>

# include<cmath>

# include<cstring>

# include<algorithm>

using namespace std;

const int N=1005;

const double inf=1e30;

struct P

{

    int x,c,dlt;

    bool operator < (const P &a) const{

        return x<a.x;

    }

};

P p[N];

int n,v,x;

double dp[N][N][2],s[N];

double dfs(int l,int r,int k)

{

    if(dp[l][r][k]>-1.0) return dp[l][r][k];

    if(l==r){

        double t=fabs((double)x-(double)p[l].x)/(double)v;

        dp[l][r][k]=s[n]*t+p[l].c;

        return dp[l][r][k];

    }

    if(k==0){

        double a=dfs(l+1,r,0);

        double b=dfs(l+1,r,1);

        double t1=(double)(p[l+1].x-p[l].x)/(double)v;

        double t2=(double)(p[r].x-p[l].x)/(double)v;

        double d=s[l]+s[n]-s[r];

        dp[l][r][k]=min(a+d*t1,b+d*t2)+(double)p[l].c;

    }else{

        double a=dfs(l,r-1,0);

        double b=dfs(l,r-1,1);

        double t1=(double)(p[r].x-p[l].x)/(double)v;

        double t2=(double)(p[r].x-p[r-1].x)/(double)v;

        double d=s[l-1]+s[n]-s[r-1];

        dp[l][r][k]=min(a+d*t1,b+d*t2)+p[r].c;

    }

    return dp[l][r][k];

}

void look()

{

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

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

            printf("%.lf ",dp[i][j][0]);

        cout<<endl;

    }

    cout<<endl;

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

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

            printf("%.lf ",dp[i][j][1]);

        cout<<endl;

    }

}

int main()

{

    //freopen("UVA-1336 Fixing the Great Wall.txt","r",stdin);

    while(~scanf("%d%d%d",&n,&v,&x))

    {

        if(n+v+x==0) break;

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

            scanf("%d%d%d",&p[i].x,&p[i].c,&p[i].dlt);

        sort(p+1,p+n+1);

        s[0]=0.0;

        for(int i=1;i<=n;++i) s[i]=s[i-1]+(double)p[i].dlt;

        memset(dp,-1.0,sizeof(dp));

        printf("%d\n",(int)min(dfs(1,n,0),dfs(1,n,1)));

        //look();

    }

    return 0;

}

巴特西

UVA-1336 Fixing the Great Wall（区间DP）

最新文章

热门文章