USACO 2016 February Contest Gold T2: Circular Barn Revisited

题目大意

还是这个谷仓，有n(3<=n<=100)个房间。当然，奶牛可能不止n头了。奶牛都在谷仓外面。现在约翰想要让第i个房间关ri（1<=ri<=1000000）头奶牛按顺时针方向走，直到到达合适的房间。这k(1<=k<=7)个门开在哪里，才能使得奶牛们走的路程最少。奶牛在谷仓外可以随意移动，可以随意选择k个门中的任意一个排队，这不计入最终的路程。

题目分析

观察数据范围，n与k都极小，不难想到一个 O(n^3 k)的dp。

第一层枚举起始位置（破环成链后链首位置），这个可以用C++自带的rotate函数实现。

然后就是一个正常的DP了，dp[i][j]表示第 i 个门开在 j 处的距离。可得转移方程为

　　 dp[i][j] = min( dp[i-1][p](上一个门开在p处的代价) + v(当前门的代价)，dp[i][j]);

#include<bits/stdc++.h>
using namespace std;
const int MAXN=205;
typedef long long ll;
const ll Inf=1e18+7;
int n,k;
ll a[MAXN];
ll f[10][MAXN];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i)
        scanf("%lld",&a[i]);
    ll res=Inf;
    for(int S=0;S<n;++S){
        memset(f,0x3f,sizeof(f));
        f[0][n]=0;
        
        for(int kk=1;kk<=k;++kk)
            for(int j=0;j<n;++j){
                ll v=0;
                for(int p=j+1;p<=n;++p){
                    v+=a[p-1]*(p-j-1);
                    f[kk][j]=min(f[kk][j],v+f[kk-1][p]);
                }
            }
        res=min(res,f[k][0]);
        rotate(a,a+1,a+n);
    }
    printf("%lld
",res);
    return 0;
}