Ptz A2: Abstract Circular Cover

这是Ptz中的一道题目。我应该补更多的题！Orz um_nik, Orz SpbSU

警告：这场比赛可能会变成未来的OpenCup或者在某些地方重现，如果你感兴趣在某些机会中打这个比赛，请别看这个blog……

题目：有一个n个点的环，你需要将每一个点恰好覆盖一次。有n*n种环上区间，长度是从0到n-1，覆盖的点的个数是从1到n（覆盖一个点只需要0的长度）。区间的费用是给出的，你需要输出对于每个k，使用恰好k个区间覆盖所有n个点、每个点只被覆盖一次的最小代价。

题解如下(OCR太好用了)

Let’s firstly solve the problem for one given .
In fact, our problem is to find points at which we split our cycle onto circular segments. This problem would be much simpler if we had a line instead of a circle. So, let’s guess one of the points at random. If we guess one point correctly, it would suffice to run dynamic programming on a line in The answer contains distinct points, so we guess one of them with probability That’s it, in order to get error probability we have to repeat the process times, achieving the total complexity of
Now back to our problem. Note that dp for segments also compute answers for every number of segments smaller than Then, in order to achieve probability (note additional factor we have to repeat the process only times for each

   

Therefore, the total complexity is
Note that it is only the upper bound, and in practice, the probability of error is smaller giving the total complexity about

um_nik提供了确定性做法，他的做法是先求出k=1,2,3,…30和k = 30,60,90,…,840的答案，然后进行答案合并。我实现了um_nik的做法

需要补更多题！明天开始的三天是最后三场比赛。。好好打！补更多题！更认真的学习。。

需要开个博客记录我补题/理解题目解法进度吗？或许。

然后可能去上海旅游了。

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}

const int N = 855,inf = 1e9+10;

int n,C[N][N],dp[N][31][N],dp2[N][31][N],dp3[N][31][N];

int main() {
    read(n);
    memset(dp2,63,sizeof(dp2));
    memset(dp,63,sizeof(dp));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            read(C[i][(i+j)%n]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int c = (i+j)%n,c1 = (c+1)%n;
            dp[i][1][c] = C[i][c];
            for(int k=1;k<30;k++){
                if(dp[i][k][c]>inf)continue;
                for(int l=j+1;l<n-i;l++){
                    int d = i+l;
                    dp[i][k+1][d] = min(dp[i][k+1][d],dp[i][k][c]+C[c1][d]);
                }
                for(int l=max(j+1,n-i);l<n;l++){
                    int d = i+l-n;
                    dp[i][k+1][d] = min(dp[i][k+1][d],dp[i][k][c]+C[c1][d]);
                }
            }
        }
    }
    
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)C[i][j] = dp[i][30][j];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int c = (i+j)%n,c1 = (c+1)%n;
            dp2[i][1][c] = C[i][c];
            for(int k=1;k<30;k++){
                if(dp2[i][k][c]>inf)continue;
                for(int l=j+1;l<n-i;l++){
                    int d = i+l;
                    dp2[i][k+1][d] = min(dp2[i][k+1][d],dp2[i][k][c]+C[c1][d]);
                }
                for(int l=max(j+1,n-i);l<n;l++){
                    int d = i+l-n;
                    dp2[i][k+1][d] = min(dp2[i][k+1][d],dp2[i][k][c]+C[c1][d]);
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<31;j++){
            for(int k=0;k<n;k++){
                dp3[k][j][i] = dp[i][j][k];
            }
        }
    }
    for(int i=1;i<=n;i++){
        int a = i/30,b = i%30,ans = inf;
        for(int l=0;l<n;l++){
            if(a == 0){
                ans = min(ans,dp[l][b][(l+n-1)%n]);
            }else{
                if(b == 0){
                    ans = min(ans,dp2[l][a][(l+n-1)%n]);
                }else{
                    int C =(l+n-1)%n;
                    for(int r = 0;r+1<n;r++){
                        ans = min(ans,dp2[l][a][(l+r)%n]+dp3[C][b][(l+r+1)%n]);
                    }
                }
            }
        }
        cout<<ans<<" \n"[i == n];
    }
    return 0;
}