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

Alex_Eon · 2023-05-05 16:00:06 · 题解

博客内食用效果更佳

思路：环形 DP
时间复杂度：O(n^3k)

本题解题目中所给最多能打开的门数量用 K 表示，题解中的 k 均为循环变量。

设 F_{i,j} 为打开 i 号门后一共打开 j 个门的总路程最小值，得到转移方程：

F_{i,j}=\min\left\{F_{k,j-1}+sum_{k,i}\right\}

其中 k 为枚举的在 i 之前最近的打开的门，sum_{k,i} 表示从门 k 转移到 i 所产生的路程和，需要进行预处理。

因为是环形 DP，所以考虑将原数组增长一倍进行，并枚举每一个节点作为第一个打开的门进行 DP，最后统计答案时要加上最后一个门到起点门之间的贡献，即：

ans=\min\left\{F_{i,K}+sum_{i,st}\right\}

其中 st 为枚举的起点。

代码实现需要注意的地方：

因为做了增长，所以预处理 sum_{i,j} 时需要考虑 i\in\left[n+1,2n-1\right] 的情况。
枚举 F_{i,j} 时，若 i 到 st 的距离小于 K，则 j 无需枚举到 K，只需要枚举到 i-st+1。
每次枚举起点 st 要注意给 F 数组赋初值。
需要开 long long。

代码中 sum_{i,j} 保证严格 i<j。
参考代码：

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;

const int N=201;

int n,K;
LL a[N],sum[N][N];

LL ans=INT_MAX,f[N][8];

int main()
{
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i+n]=a[i]; //增长
    }

    for(int i=1;i<=2*n-1;i++)
        for(int j=i+2;j<=min(2*n,i+n);j++)//注意边界判断
            sum[i][j]=sum[i][j-1]+a[j-1]*(j-i-1);
    for(int st=1;st<=n;st++)
    {
        memset(f,0x3f,sizeof(f));
        f[st][1]=0;
        for(int i=st+1;i<=st+n-1;i++)
        {
            int temp=min(i-st+1,K);//j 枚举范围
            for(int j=2;j<=temp;j++)
                for(int k=st;k<i;k++)
                    f[i][j]=min(f[i][j],f[k][j-1]+sum[k][i]);
        }
        for(int i=st+K-1;i<=st+n-1;i++)
            ans=min(ans,f[i][K]+sum[i][st+n]);//st+n 保证 i<st+n
    }

    printf("%lld",ans);
    return 0;
}