APIO2007[数据备份/backup]

首先，很容易想到动态规划，然后，由于时间复杂度为O(n*k)，当然只能拿部分分。

所以，看了题解，用贪心法做。

然后，当k=1时，显然，我们贪最短的线段。

假设我们得到了k=n时的最优解，然后如何从n推到n+1呢？

看下图：

（注：两绿框间的狭缝里是有小黑点的，图不是很清楚。）

现在已有8条蓝线，且这是最优的（我们假设哈，图画的不好，不像是最优的）。

那么，我们要加一条线，就只需将其中一个part的红与蓝换色，然后费用就是改变后的蓝线长度和减去原来的长度和。然后贪最小的来改色。

然后关于part的划分，一个part是指以红色线段开头且结尾也为红色线段，中间一红一蓝相隔的几条连续线段。

这样贪，从n=1贪到n=k，然后就完了。

具体实现需要用到二叉堆。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-20

DESCRIPTION:

$DESCRIPTION

*/

#include <fstream>

using std::ifstream;

using std::ofstream;

using std::endl;

#include <vector>

using std::vector;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::min;

#include <queue>

using std::priority_queue;

#include <iostream>

using std::cin;

using std::cout;

 

class Application

{

      static const unsigned int oo=1000000000;

      //ifstream cin;

      //ofstream cout;

      int n,k;

      vector<unsigned int> s;

      public:

      Application(const char* input,const char* output)

                        //:cin(input),cout(output)

      {

                        cin>>n>>k;

                        s.resize(n);

                        for (vector<unsigned int>::iterator it=s.begin();

                                                            it!=s.end();

                                                            it++)

                            cin>>*it;

      }

      int run()

      {

          int m=n-1;

          vector<int> left(m+2);

          vector<int> right(m+2);

          vector<int> value(m+2);

          vector<bool> deleted(m+2,false);

         

          value[0]=oo;

          for (int i=1;i<=m;i++)

          {

              left[i]=i-1;

              right[i]=i+1;

              value[i]=s[i]-s[i-1];

          }

          value[m+1]=oo;

         

          priority_queue<pair<int,int>,

                         vector<pair<int,int> >,

                         std::greater<pair<int,int> > > q;

          for (int i=1;i<=m;i++)

              q.push(make_pair(value[i],i));

         

          int answer=0;

          for (int i=0;i<k;i++)

          {

              while (deleted[q.top().second]) q.pop();

              deleted[left[q.top().second]]=true;

              deleted[right[q.top().second]]=true;

             

              answer+=value[q.top().second];

             

              value[q.top().second]

              =value[left[q.top().second]]

              +value[right[q.top().second]]

              -value[q.top().second];

              right[left[left[q.top().second]]]=left[right[right[q.top().second]]]=q.top().second;

              left[q.top().second]=left[left[q.top().second]];

              right[q.top().second]=right[right[q.top().second]];

             

              q.push(make_pair(value[q.top().second],q.top().second));

              q.pop();

          }

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app(“backup.in”,“backup.out”);

    return app.run();

}