BZOJ 1150:[APIO/TSC 2007]データバックアップ——問題解

6736 ワード
https://www.lydsy.com/JudgeOnline/problem.php?id=1150
IT会社では、大規模なオフィスビルやオフィスビルのコンピュータデータをバックアップしています.しかし、データバックアップの仕事は退屈なので、異なるオフィスビルを互いにバックアップし、家に座ってコンピュータゲームを楽しむシステムを設計したいと思っています.
オフィスビルは同じ通りにあることが知られています.あなたはこれらのオフィスビルにペアを組むことにしました(2つのグループ).各オフィスビルは、この2つの建物の間にネットワークケーブルを敷設することで、互いにバックアップすることができます.
しかし、ネットワークケーブルの費用は高い.ローカルテレコムはK本のネットワークケーブルしか提供できません.これは、K対オフィスビル(または合計2 Kのオフィスビル)のバックアップのみを手配できることを意味します.いずれのオフィスビルも唯一のペアグループに属している(言い換えれば、この2 Kのオフィスビルはきっと違うに違いない).
また、電信会社はネットワークケーブルの長さ(キロ数)で料金を徴収する必要があります.そのため、このK対オフィスビルを選択して、ケーブルの全長をできるだけ短くする必要があります.言い換えれば、このK対のオフィスビルを選択して、各対のオフィスビル間の距離の和(総距離)をできるだけ小さくする必要があります.
次の例では、5人のお客様がオフィスビルが1つの街にあると仮定します.下図に示します.この5つのオフィスビルは、通りの起点から1 km、3 km、4 km、6 km、12 kmに位置しています.電信会社はK=2本のケーブルしか提供していません.
上記の例では、1番目と2番目のオフィスビルを接続し、3番目と4番目のオフィスビルを接続するのがベストです.これにより、K=2本のケーブルを要求通りに使用することができる.1本目のケーブルの長さは3 km-1 km=2 km、2本目のケーブルの長さは6 km-4 km=2 kmです.このペアリングスキームは,距離の和の最小の要件を満たす全長4 kmのネットワークケーブルを必要とする.
簡単な思考(trick)次元の問題が必要です.
隣の2つのオフィスビルしか取れないことに気づいたら、dpを書くことができて、言わないでください.
欲張りを考えて取りに行きます:私たちはすべてのオフィスビルの距離を山の中に入れて、それから毎回最小を弾いて、しかも弾いた両側のオフィスビルはもう取れません.よろしいでしょうか.
明らかにだめです.サンプルは反例です.2 1 2 6です.1を取った後、6しか取れません.結果は7を出力しました.
そこで、プログラムに「後悔」の機会を与えます.ポップアップされた両側のオフィスビルをペアにし、その距離は2つのオフィスビルのペアの距離と-ポップアップされたオフィスビルの距離です.
このように私たちがこのペアを取ったとき、中間のペアを減らして隣の両側のペアを取ったのと同じように、「後悔」の過程です.
メンテナンス両側のペアはチェーンテーブルで実現できます.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
const int N=1e5+5;
const int INF=1e9+1;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
mapbool>mp;
priority_queue,greater >q;
int n,k,a[N],pre[N],nxt[N];
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i){
        a[i]=a[i+1]-a[i];
        pre[i]=i-1;nxt[i-1]=i;
        q.push(pii(a[i],i));
    }
    nxt[n-1]=n;pre[0]=0;nxt[n]=n;a[0]=a[n]=INF;
    int ans=0;
    while(k--){
        pii p=q.top();q.pop();
        if(mp.count(p)){k++;mp.erase(p);continue;}
        ans+=p.fi;
        a[p.se]=a[pre[p.se]]+a[nxt[p.se]]-p.fi;
        mp[pii(a[pre[p.se]],pre[p.se])]=1;
        mp[pii(a[nxt[p.se]],nxt[p.se])]=1;
        q.push(pii(a[p.se],p.se));
        pre[p.se]=pre[pre[p.se]];
        nxt[p.se]=nxt[nxt[p.se]];
        nxt[pre[p.se]]=p.se;
        pre[nxt[p.se]]=p.se;
    }
    printf("%d
",ans);
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++
+著者:luyouqi 233.　　　　　　　　　　　　　　+
+ブログへようこそ:http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++
転載先:https://www.cnblogs.com/luyouqi233/p/9217142.html
PostgreSQLのポイント・イン・タイム・リカバリ(PITR)ベース
実験棟試合19のバックアップログファイル