[洛谷P1220]关路灯

这是一道区间动态规划题

项目分析
状态$dp[l][r][k]$,代表关掉$l \sim r$区间所有灯且在左端点($k=0$),右端点($k=1$)
阶段区间的长度len
决策$dp[l][r][0]=min(dp[l+1][r][0]+cost(左),dp[l+1][r][1]+cost(右)$(右端点略)
边界$dp[c][c][0]=dp[c][c][1]=0$(起始点瞬间关灯)
答案$min(dp[1][n][0],dp[1][n][1])$

参考代码:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 51;

int n,c;
int poss[MAXN],engs[MAXN];

int dp[MAXN][MAXN][2];

int cost(int a, int b, int l, int r) {
    return (poss[a] - poss[b]) * (engs[n] + engs[l] - engs[r]);
}

int main() {
    ios::sync_with_stdio(false);

    memset(dp, 0x3F3F3F, sizeof(dp));

    cin >> n >> c;

    int x;
    for ( int i = 1; i <= n; ++i ) {
        cin >> poss[i] >> x;
        engs[i] = engs[i - 1] + x;
    }

    dp[c][c][0] = dp[c][c][1] = 0;

    for ( int len = 2; len <= n; ++len ) 
        for ( int i = 1; i <= n - len + 1; ++i ) {
            int l = i;
            int r = i + len - 1;
            dp[l][r][0] = min(dp[l + 1][r][0] + cost(l + 1, l, l, r),dp[l + 1][r][1] + cost(r, l, l, r));
            dp[l][r][1] = min(dp[l][r - 1][0] + cost(r, l, l - 1, r - 1), dp[l][r - 1][1] + cost(r, r - 1, l - 1, r - 1));
        }

    cout << min(dp[1][n][0], dp[1][n][1]) << endl;

    return 0;
}

边界处理有些繁琐,需要细心仔细。


拓展与思考:

要是关灯的时间各不相同呢?

Last modification:September 4th, 2019 at 09:14 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment