专栏文章

【题解】P6173 [USACO16FEB] Circular Barn P

OOneLeft
P6173题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipacp93
此快照首次捕获于
2025/12/03 08:45
3 个月前
此快照最后确认于
2025/12/03 08:45
3 个月前
查看原文

题意

有顺时针编号的 nn 个房间，房间 ii 有 rir_i 头奶牛，你需要在这些房间中开 kk 扇门，每个奶牛会从某个门进入，然后顺时针行走到自己的谷仓，求奶牛行走距离总和的最小值。

思路

在一个环上比较难考虑，因此我们断环为链，这里需要 O(n)O(n) 的时间复杂度。
设 dpi,jdp_{i,j} 为前 ii 个房间开 jj 扇门时奶牛行走距离的总和，则有转移方程如下：
dpi,j=min⁡k=0i−1dpk,j−1+w(k+1,i)dp_{i,j}=\min_{k=0}^{i-1}dp_{k,j-1}+w(k+1,i)
其中 w(i,j)w(i,j) 为在房间 ii 开门，房间编号为 i∼ji\sim j 的奶牛的行走距离总和，可以 O(n2)O(n^2) 预处理出来。
这个做法是 O(n3k)O(n^3k) 的，无法通过此题，但是可以通过此题的弱化版。
通过打表可以发现对于 a≤b≤c≤da\le b\le c\le d 有 w(a,c)+w(b,d)≤w(a,d)+w(b,c)w(a,c)+w(b,d)\le w(a,d)+w(b,c)，证明如下：
w(a,c)=ra+1+2ra+2+⋯+(c−a)acw(a,d)=ra+1+2ra+2+⋯+(d−a)adw(a,d)−w(a,c)=(c+1−a)ac+1+(c+2−a)ac+2+⋯+(d−a)adw(b,d)=rb+1+2rb+2+⋯+(d−b)adw(b,c)=rb+1+2rb+2+⋯+(c−b)acw(b,c)−w(b,d)=−(c+1−b)ac+1−(c+2−b)ac+2−⋯−(d−b)adw(a,d)+w(b,c)−w(a,c)−w(b,d)=(b−a)ac+1+(b−a)ac+2+⋯+(b−a)adw(a,d)+w(b,c)−w(a,c)−w(b,d)≥0w(a,c)+w(b,d)≤w(a,d)+w(b,c)w(a,c)=r_{a+1}+2r_{a+2}+\dots+(c-a)a_c\\ w(a,d)=r_{a+1}+2r_{a+2}+\dots+(d-a)a_d\\ w(a,d)-w(a,c)=(c+1-a)a_{c+1}+(c+2-a)a_{c+2}+\dots+(d-a)a_d\\ w(b,d)=r_{b+1}+2r_{b+2}+\dots+(d-b)a_d\\ w(b,c)=r_{b+1}+2r_{b+2}+\dots+(c-b)a_c\\ w(b,c)-w(b,d)=-(c+1-b)a_{c+1}-(c+2-b)a_{c+2}-\dots-(d-b)a_d\\ w(a,d)+w(b,c)-w(a,c)-w(b,d)=(b-a)a_{c+1}+(b-a)a_{c+2}+\dots+(b-a)a_d\\ w(a,d)+w(b,c)-w(a,c)-w(b,d)\ge0\\ w(a,c)+w(b,d)\le w(a,d)+w(b,c)
满足四边形不等式，故满足决策单调性，考虑使用分治优化，最终时间复杂度为 O(n2klog⁡n)O(n^2k\log n)，可以通过此题。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5,M=15,inf=(int)4e18+5;
int a[N<<1],w[N<<1][N<<1],dp[N][M];
void solve(int bgn,int id,int l,int r,int lpt,int rpt)
{
	if(l>r)return;
	int mid=l+r>>1,opt;
	for(int i=lpt;i<=min(mid,rpt);i++)
	{
		int val=dp[i][id-1]+w[i+bgn][mid+bgn-1];
		if(dp[mid][id]>val)dp[mid][id]=val,opt=i;
	}
	solve(bgn,id,l,mid-1,lpt,opt),solve(bgn,id,mid+1,r,opt,rpt);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
	for(int i=1;i<=(n<<1);i++)
	for(int j=i+1;j<=(n<<1);j++)
		w[i][j]=w[i][j-1]+a[j]*(j-i);
	int ans=inf;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<N;j++)
		for(int k=0;k<M;k++)
			dp[j][k]=inf;
		for(int j=1;j<=m;j++)solve(i,j,0,n,0,n);
		ans=min(ans,dp[n][m]);
	}
	cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...