P1220 关路灯——简单的区间dp

· · 个人记录

拿到题目之后想到可以用dp做

然后就开始乱想：

没什么意义的O(n^4)解法

设dp_{l,r}为关闭了[l,r]这段灯之后的耗费的最小电能

然后考虑状态转移的时候发现不对，需要记录关掉的最后一盏灯

接下来这个人又抽风了，之后想状态的时候脑子里想的变成更新到[l,r]这段距离的时候内部消耗的电能的最小值

于是为了状态转移，有多记录了一维时间

时间的最大值考虑最坏情况应当是n^2级别

于是状态就变成了dp_{l,r,k,t}为t时刻，关完[l,r]内的所有灯，最后在k端点关闭时更新到的区域内的的最小耗电量(初见端倪)

但是这样空间复杂度达到了惊人的O(n^5),连50的数据都带不动这么逆天的东西了

考虑优化，可以发现关灯的区间必然是连续的，也就是说老张走到哪灯就会关到哪，否则必然有等效的更优解

所以说事实上k只有两种情况，左端点和右端点

于是状态优化成了dp_{l,r,0/1,t},意义是t时刻，关完[l,r]内的所有灯，最后在左/右端点时更新到的区域内的的最小耗电量

考虑转移，对于左端点，只可能是由原本的区间向左拓展来的，也就是说只有两种情况，从那个区间的左/右端点跑过来

dp_{l,r,0,t}=min(dp_{l+1,r,0,t-dis_{l,l+1}}+dis_{l,l+1}\times P_l,p_{l+1,r,1,t-dis_{l,r}}+dis_{l,r}\times P_l)

右端点同理

时间复杂度O(n^4)

AC Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=55;
const int inf=0x3f3f3f3f;

int dp[MAXN][MAXN][MAXN*MAXN][2];//t时刻，关完[i,j]内的所有灯，最后在左/右端点时更新到的区域内的的最小耗电量 

int p[MAXN],a[MAXN];

int n,c;

int dis(int x,int y){
    return abs(a[x]-a[y]);
}//

int res=inf;

void work(){
    //input...
    scanf("%d%d",&n,&c);

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

    memset(dp,inf,sizeof(dp));

    dp[c][c][0][0]=dp[c][c][0][1]=0;
    for(int t=0;t<=n*n;++t){
        for(int i=c+1;i<=n;++i)
            if(t-dis(i,i-1)>=0)
                dp[c][i][t][1]=dp[c][i-1][t-dis(i-1,i)][1]+t*p[i];
        for(int i=c-1;i>=1;--i)
            if(t-dis(i+1,i)>=0)
                dp[i][c][t][0]=dp[i+1][c][t-dis(i+1,i)][1]+t*p[i];
        for(int r=c+1;r<=n;++r)
            for(int l=c-1;l>=1;--l){
                if(t-dis(r,r-1)>=0)
                    dp[l][r][t][1]=min(dp[l][r][t][1],dp[l][r-1][t-dis(r,r-1)][1]+t*p[r]);
                if(t-dis(r,l)>=0)
                    dp[l][r][t][1]=min(dp[l][r][t][1],dp[l][r-1][t-dis(r,l)][0]+t*p[r]);
            }
        for(int l=c-1;l>=1;--l)
            for(int r=c+1;r<=n;++r){
                if(t-dis(l,l+1)>=0)
                    dp[l][r][t][0]=min(dp[l][r][t][0],dp[l+1][r][t-dis(l,l+1)][0]+t*p[l]);
                if(t-dis(r,l)>=0)
                    dp[l][r][t][0]=min(dp[l][r][t][0],dp[l+1][r][t-dis(r,l)][1]+t*p[l]);
            }

        for(int r=1;r<=n;++r)
            for(int l=1;l<=r;++l){
                if(t-dis(r,r-1)>=0)
                    dp[l][r][t][1]=min(dp[l][r][t][1],dp[l][r-1][t-dis(r,r-1)][1]+t*p[r]);
                if(t-dis(r,l)>=0)
                    dp[l][r][t][1]=min(dp[l][r][t][1],dp[l][r-1][t-dis(r,l)][0]+t*p[r]);
                if(t-dis(r,l)>=0)
                    dp[l][r][t][0]=min(dp[l][r][t][0],dp[l+1][r][t-dis(r,l)][1]+t*p[l]);
                if(t-dis(l+1,l)>=0)
                    dp[l][r][t][0]=min(dp[l][r][t][0],dp[l+1][r][t-dis(l+1,l)][0]+t*p[l]);
            }
        res=min(res,min(dp[1][n][t][0],dp[1][n][t][1]));
    }//

    printf("%d",res);
}

int main(){
    work();
    return 0;
}

O(n^2)正解

事实上之前搞成那个鬼样子都是因为中途把自己设计的状态搞错了

事实上如果是维护全局的耗电量的话，是不需要维护时间维的

那末状态就可爱多了，dp_{l,r,0/1}意义是[l,r]内的灯全部关完，且在左/右端点结束所耗费的最小电能

状态转移方程差不多，直接看代码吧

要注意的是这里要用前缀和来算区间总功率

AC Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=55;
const int inf=0x3f3f3f3f;

int a[MAXN],sum[MAXN];
int dp[MAXN][MAXN][2];
int n,c;

int dis(int x,int y){
    return abs(a[x]-a[y]);
}//

int query(int l,int r){
    return sum[r]-sum[l-1];
}//

void work(){
    scanf("%d%d",&n,&c);
    int p,r;

    for(int i=1;i<=n;++i){
        scanf("%d%d",&a[i],&p);
        sum[i]=sum[i-1]+p;
    }

    memset(dp,inf,sizeof(dp));
    dp[c][c][0]=dp[c][c][1]=0;
    for(int len=2;len<=n;++len){
        for(int l=1;l+len-1<=n;++l){
            r=l+len-1;
            dp[l][r][0]=min(
            dp[l+1][r][0]+dis(l+1,l)*(query(1,n)-query(l+1,r)),//左端点跑过来 
            dp[l+1][r][1]+dis(l,r)*(query(1,n)-query(l+1,r))); //右端点跑过来 

            dp[l][r][1]=min(
            dp[l][r-1][1]+dis(r-1,r)*(query(1,n)-query(l,r-1)),//右端点跑过来 
            dp[l][r-1][0]+dis(l,r)*(query(1,n)-query(l,r-1))); //左端点跑过来 
        }
    }

    printf("%d",min(dp[1][n][1],dp[1][n][0]));
}// 

int main(){
    work();
    return 0;
}