题解【P3140 [USACO16FEB] Circular Barn Revisited G】

· · 题解

题目传送门

本题的环很难处理，考虑破环成链，这里介绍一个函数：

std::rotate(iterator start, iterator middle, iterator end);

分别表示序列第一个元素，想要开始旋转的元素及序列最后一个元素。

在本题中，每次往后旋转一位进行 dp。定义 dp_{i,j} 表示当前开 i 道门，在第 j 个房间的最小总距离。用一个变量 s 记录 j 以后的房间到 j 的总路程，若用 l 枚举以后的房间，则 dp_{i,j} \leftarrow \min(dp_{i,j},dp_{i-1,l}+s)。每次 dp 的最后答案为 dp_{k,0}。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
#define rep(a, b, c, d) for(int a=b; a<=c; a+=d)
const int N = 1e2 + 5;
int n, K, r[N], dp[8][N];
void minn(int &q, int p) {
    q = min(q, p);
}
signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> K;
    for(int i = 0; i < n; ++ i)
        cin >> r[i];
    int ans = 1145141919810364364;
    for(int i = 0; i < n; ++ i) { // 枚举环的开始
        memset(dp, 127, sizeof dp);
        dp[0][n] = 0; // 初始化
        for(int k = 1; k <= K; ++ k) // 枚举开门数
            for(int j = 0; j < n; ++ j) { // 枚举所在房间
                int s = 0;
                for(int l = j + 1; l <= n; ++ l) { // 枚举以后的房间
                    s += r[l - 1] * (l - j - 1); // 计算距离
                    minn(dp[k][j], dp[k - 1][l] + s); // 状态转移
                }
            }
        minn(ans, dp[K][0]); // 更新答案
        rotate(r, r + 1, r + n); // 后旋一位
    }
    cout << ans;
    return 0;
}

题解来之不易，麻烦留赞再走~

最后给个友链：P1299 切孔机，题号最小能发题解题目。