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 k.
In fact, our problem is to find k 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 O\left(n^{2} k\right) . The answer contains k distinct points, so we guess one of them with probability \frac{k}{n} . That’s it, in order to get error probability 2^{-\varepsilon}, we have to repeat the process O\left(\frac{n}{k} \log \frac{1}{\varepsilon}\right) times, achieving the total complexity of O\left(n^{3} \log \frac{1}{\varepsilon}\right)
Now back to our problem. Note that dp for k segments also compute answers for every number of segments smaller than k . Then, in order to achieve probability 2^{-\varepsilon} \cdot n (note additional n factor ), we have to repeat the process only O\left(\left(\frac{n}{k}-\frac{n}{k+1}\right) \log \frac{1}{\varepsilon}\right) times for each k

    \[\sum_{k}\left(\frac{n}{k}-\frac{n}{k+1}\right) n^{2} k \log \frac{1}{\varepsilon}=O\left(n^{3} \log n \log \frac{1}{\varepsilon}\right)\]


Therefore, the total complexity is O\left(n^{3} \log ^{2} n \log \frac{1}{\varepsilon}\right)
Note that it is only the upper bound, and in practice, the probability of error is smaller giving the total complexity about O\left(n^{3} \log n \log \frac{1}{\varepsilon}\right)

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;
}

《Ptz A2: Abstract Circular Cover》上有2条评论

Okazaki Yumemi进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注