Boleyn Su's Blog

树形动规。

然后，若上司去了，那么下属一定不能去；若上司不去，那么下属可去可不去。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-22

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int oo=~(1<<31);

      int N;

      vector<int> happy;

      vector<vector<int> > children;

      vector<vector<int> > f;

      int dp(int parent,bool join)

      {

          if (f[parent][join]!=-oo) return f[parent][join];

          int max=-oo;

          //CASE 1 MY PARENT WANNA JOIN THE PARTY

          if (join)

          {

             int get=happy[parent];

             for (int i=0;i<children[parent].size();i++)

                 get+=dp(children[parent][i],false);

             if (get>max) max=get;

          }

          //CASE 2 MY PARENT HATE PARTIES

          else

          {

             int get=0;

             for (int i=0;i<children[parent].size();i++)

             {

                 int joinit=dp(children[parent][i],true);

                 int hateit=dp(children[parent][i],false);

                 if (joinit>hateit) get+=joinit;

                 else get+=hateit;

             }

             if (get>max) max=get;        

          }

          return f[parent][join]=max;

      }

      public:

      Application()

      {

                    //WE WANNA A ROOT, SO WE ADD A NODE 0.

                    cin>>N;

                    happy.resize(N+1);

                    happy[0]=0;

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

                        cin>>happy[i];

                    children.resize(N+1);

                    vector<bool> haveParent(N+1,false);

                    for (;;)

                    {

                        int L,K;

                        cin>>L>>K;

                        if (L==0&&K==0) break;

                        children[K].push_back(L);

                        haveParent[L]=true;

                    }

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

                        if (!haveParent[i])

                           children[0].push_back(i);

      }

      int run()

      {

          f.resize(N+1,vector<int>(2,-oo));

          cout<<dp(0,false)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，但是我被水了。

提示：

letter的定义是letter={所有的字母，即a到z和A到Z}。

然后任何letter后有大写字母则错，任何句子第一个letter为小写字母则错。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-22

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <cstdio>

//using std::EOF;

 

class Application

{

      string file;

      int mistake;

      public:

      Application()

                   :mistake(0)

      {

                    char get;

                    while ((get=cin.get())!=EOF) file.push_back(get);

      }

      int run()

      {

          vector<bool> upper(256,false),

                       lower(256,false),

                       letter(256,false),

                       endofsentence(256,false);

          for (char i=’A’;i<=’Z’;i++) upper[i]=true;

          for (char i=’a’;i<=’z’;i++) lower[i]=true;

          for (char* i=“ABCDEFGHIJKLMNOPQRSTUVWXYZ”

                       “abcdefghijklmnopqrstuvwxyz”;*i;i++)

              letter[*i]=true;

          for (char* i=“.?!”;*i;i++)

              endofsentence[*i]=true;

         

          //CASE 1

          for (int i=1;i<file.length();i++)

              if (upper[file[i]]&&letter[file[i-1]])

                 mistake++;

          //CASE 2

          for (int i=0,j;i<file.length();i=j+1)

          {

              for (j=i;j<file.length()&&(!endofsentence[file[j]]);j++) ;

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

              {

                  if (lower[file[k]])

                     mistake++;

                  if (letter[file[k]])

                     break;

              }

              //cout<<“sentence:”<<i<<“,”<<j<<endl;

              //for (int k=i;k<=j;k++) cout<<file[k];

              //cout<<endl;

          }

         

          cout<<mistake<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

又是线段树，讨厌的线段树。写惨了。囧。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-21

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int T=600;

      static const int N=30000;

      static const int oo=~(1<<31);

      vector<int> block,st;

      void change(int now,int l,int r,int id)

      {

           int mid=(l+r)/2;

           if (l==id&&r==id) st[now]=block[id];

           else

           {

               if (l<=id&&id<=mid)

                  change(now*2,l,mid,id);

               if (mid+1<=id&&id<=r)

                  change(now*2+1,mid+1,r,id);

              

               if (st[now*2]<st[now*2+1]) st[now]=st[now*2];

               else st[now]=st[now*2+1];

           }

      }

      int findmin(int now,int l,int r,int time)

      {

          int mid=(l+r)/2;

          if (l==r) return mid;

          if (st[now*2]<time) return findmin(now*2,l,mid,time);

          else return findmin(now*2+1,mid+1,r,time);

      }

      bool update(int id,int time)

      {

           if (block[id]<time) return false;

           else

           {

               block[id]=time+T-1;

               change(1,0,N-1,id);

               return true;

           }

      }

      int get(int time)

      {

          int find=findmin(1,0,N-1,time);

          block[find]=time+T-1;

          change(1,0,N-1,find);

          return find;

      }

      public:

      Application()

                   :block(N,-oo),st(N*4,-oo)

      {

      }

      int run()

      {

          int time;

          while (cin>>time)

          {

                char order;

                cin>>order;

                if (order==’.’)

                {

                   int blockid;

                   cin>>blockid;

                   if (update(blockid-1,time)) cout<<“+”<<endl;

                    else cout<<“-“<<endl;

                }

                else cout<<get(time)+1<<endl;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

无聊的递推。

方程：

f[i][j]表示j个苹果放到i个容量为9的盒子一共有多少种放法。

那么f[i][j]=sum{f[i-1][k],0<=j-k<=9}。

最后，我被水了，先是没有写高精度，然后是没有判断S是否为偶数。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-21

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <iomanip>

 

class BigNumber

{

      static const int BASE=10000;

      vector<int> d;

      public:

      BigNumber(int value=0)

                    :d(1,value)

      {

                    //assert(value<BASE);

      }

      friend BigNumber operator+(const BigNumber& a,const BigNumber& b)

      {

             BigNumber c;

             c.d.resize(a.d.size()>b.d.size()?a.d.size():b.d.size());

             int over=0;

             for (int i=0;i<c.d.size();i++)

                 if (i<a.d.size()&&i<b.d.size())

                 {

                    c.d[i]=(a.d[i]+b.d[i]+over)%BASE;

                    over=(a.d[i]+b.d[i]+over)/BASE;

                 }

                 else if (i<a.d.size())

                 {

                    c.d[i]=(a.d[i]+over)%BASE;

                    over=(a.d[i]+over)/BASE;

                 }

                 else if (i<b.d.size())

                 {

                    c.d[i]=(b.d[i]+over)%BASE;

                    over=(b.d[i]+over)/BASE;

                 }

             if (over) c.d.push_back(over);

             return c;

      }

      friend BigNumber operator*(const BigNumber& a,const BigNumber& b)

      {

             BigNumber c;

             c.d.resize(a.d.size()+b.d.size(),0);

             for (int i=0;i<a.d.size();i++)

                 for (int j=0;j<b.d.size();j++)

                 {

                     c.d[i+j]+=a.d[i]*b.d[j];

                     if (c.d[i+j]>=BASE)

                     {

                        c.d[i+j+1]+=c.d[i+j]/BASE;

                        c.d[i+j]=c.d[i+j]%BASE;

                     }

                 }

             if (!c.d.back()) c.d.pop_back();

             return c;

      }

      BigNumber& operator+=(BigNumber& add)

      {

                 *this=operator+(*this,add);

                 return *this;

      }

      BigNumber& operator*=(int mul)

      {

                 int over=0;

                 for (int i=0;i<d.size();i++)

                 {

                     int old=d[i];

                     d[i]=(old*mul+over)%BASE;

                     over=(old*mul+over)/BASE;

                 }

                 if (over) d.push_back(over);

                 return *this;

      }

      BigNumber& operator/=(int div)

      {

                 int rest=0;

                 for (int i=d.size()-1;i>=0;i–)

                 {

                     int old=d[i];

                     d[i]=(rest*BASE+old)/div;

                     rest=(rest*BASE+old)%div;

                 }

                 if (d[d.size()-1]==0) d.resize(d.size()-1);

                 return *this;

      }

      void print()

      {

           cout<<d[d.size()-1];

           for (int i=d.size()-1–1;i>=0;i–)

               cout<<std::setfill(‘0’)<<std::setw(4)<<d[i]<<std::setw(1)<<std::setfill(‘ ‘);

           cout<<endl;

      }

};

 

class Application

{

      int N,S;

      public:

      Application()

      {

                    cin>>N>>S;

      }

      int run()

      {

          //答案为将S/2个苹果分到N个果盘里（最多分9个，最少不分）的方案数的平方

          //用生成函数 (1+x^2+x^3+…+x^9)^N

          //然后x^(s/2)的系数的平方

          //然后生成函数的程序我不想写了

          if (S%2)

          {

             cout<<0<<endl;

             return 0;

          }

         

          vector<vector<BigNumber> > f(N,vector<BigNumber>(S/2+1));

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

          {

              if (i)

                 for (int j=0;j<=S/2;j++)

                 {

                     f[i][j]=0;

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

                         if (j-k<=9)

                            f[i][j]+=f[i-1][k];

                 }

              else

                  for (int j=0;j<=S/2;j++)

                      if (j<=9)

                         f[i][j]=1;

          }

          BigNumber answer=f[N-1][S/2]*f[N-1][S/2];

          answer.print();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

唉，不好说，都是看了题解做的。然后黑书上有讲，自己看吧。（刘汝佳的黑书P274）

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-21

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N,M;

      vector<vector<char> > forward,backward;

      public:

      Application()

      {

                    cin>>N>>M;

                    forward.resize(N,vector<char>(M));

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

                        for (int j=0;j<M;j++)

                            cin>>forward[i][j];

                    backward.resize(N,vector<char>(M));

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

                        for (int j=0;j<M;j++)

                            cin>>backward[i][j];

      }

      int run()

      {

          vector<vector<int> > degree(N+1,vector<int>(M+1,0));

          vector<vector<bool> > link_up(N+1,vector<bool>(M+1,false)),

                              link_down(N+1,vector<bool>(M+1,false));

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

              for (int j=0;j<M;j++)

              {

                  switch (forward[i][j])

                  {

                         case ‘X’:

                              degree[i][j]++;

                              degree[i+1][j]++;

                              degree[i][j+1]++;

                              degree[i+1][j+1]++;

                              link_up[i][j]=true;

                              link_down[i][j]=true;

                              break;

                         case ‘/’:

                              degree[i+1][j]++;

                              degree[i][j+1]++;

                              link_up[i][j]=true;

                              break;

                         case ‘\\’:

                              degree[i][j]++;

                              degree[i+1][j+1]++;

                              link_down[i][j]=true;

                              break;

                         default:

                                 break;

                  }

                  switch (backward[i][j])

                  {

                         case ‘X’:

                              degree[i][j]–;

                              degree[i+1][j]–;

                              degree[i][j+1]–;

                              degree[i+1][j+1]–;

                              link_up[i][j]=true;

                              link_down[i][j]=true;

                              break;

                         case ‘/’:

                              degree[i+1][j]–;

                              degree[i][j+1]–;

                              link_up[i][j]=true;

                              break;

                         case ‘\\’:

                              degree[i][j]–;

                              degree[i+1][j+1]–;

                              link_down[i][j]=true;

                              break;

                         default:

                                 break;

                  }

              }

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

              for (int j=0;j<=M;j++)

                  if (degree[i][j]<0) degree[i][j]=-degree[i][j];

         

          int answer=0;

          queue<pair<int,int> > q;

          vector<vector<bool> > inq(N+1,vector<bool>(M+1,false));

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

              for (int j=0;j<=M;j++)

                  if (!inq[i][j])

                  {

                     int counter=0;

                     bool isABlock=false;

                    

                     q.push(make_pair(i,j));

                     inq[i][j]=true;

                     counter+=degree[i][j];

                     while (!q.empty())

                     {

                           int gi=q.front().first,

                               gj=q.front().second;

                           #define inbox(i,j) ((i>=0)&&(i<=N)&&(j>=0)&&(j<=M))

                           #define push_if(i,j,if_what)\

                           if (inbox(i,j)&&(!inq[i][j])&&(if_what))\

                           {\

                              isABlock=true;\

                              q.push(make_pair(i,j));\

                              inq[i][j]=true;\

                              counter+=degree[i][j];\

                           }

                           push_if(gi+1,gj+1,link_down[gi][gj]);

                           push_if(gi-1,gj-1,link_down[gi-1][gj-1]);

                           push_if(gi-1,gj+1,link_up[gi-1][gj]);

                           push_if(gi+1,gj-1,link_up[gi][gj-1]);

                           #undef push_if

                           #undef inbox

                           q.pop();

                     }

                     if (counter) answer+=counter/2;

                     else if (isABlock) answer++;

                  }

         

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

先选三个来变，由于开始就很和谐，为了和谐，我们就将挑出来的三个棋子进行调整（按行或列来选），一共有两种调整方案（调整列或行）。

然后，在对角线判断一下就OK了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-20

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N;

      vector<int> p;

      int total;

      public:

      Application()

      {

                   cin>>N;

                   p.resize(N);

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

                   {

                       int id,position;

                       cin>>id>>position;

                       p[id-1]=position-1;

                   }

      }

      bool can()

      {

           vector<bool> sum(N*2,false),delta(N*2,false);

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

           {

               if (sum[i+p[i]]) return false;

               else sum[i+p[i]]=true;

               if (delta[N+i-p[i]]) return false;

               else delta[N+i-p[i]]=true;

           }

           return true;

      }

      int run()

      {

          total=0;

          for (int c1=0;c1<N;c1++)

              for (int c2=c1+1;c2<N;c2++)

                  for (int c3=c2+1;c3<N;c3++)

              {

                  //backup

                  int b1=p[c1],b2=p[c2],b3=p[c3];

                  //CASE 1:

                  p[c1]=b3;

                  p[c2]=b1;

                  p[c3]=b2;

                  if (can()) total++;

                  //CASE 2:

                  p[c1]=b2;

                  p[c2]=b3;

                  p[c3]=b1;

                  if (can()) total++;

                  //recover

                  p[c1]=b1;

                  p[c2]=b2;

                  p[c3]=b3;

              }

          cout<<total<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，BFS就行了。但是要注意一下起点和终点可能会不连通，我就是因为这一点WA了几次！

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-20

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

//using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N;

      vector<vector<char> > map;

      void bfs()

      {

           int answer=0;

           queue<pair<int,int> > q;

           vector<vector<bool> > inq(N,vector<bool>(N,false));

           #define go(dx,dy)\

           {\

                   int nexti=gi+(dx),nextj=gj+(dy);\

                   if ((nexti<N)\

                      &&(nexti>=0)\

                      &&(nextj<N)\

                      &&(nextj>=0)\

                      &&(!inq[nexti][nextj])\

                      &&(map[nexti][nextj]==’.’))\

                   {\

                     q.push(make_pair(nexti,nextj));\

                     inq[nexti][nextj]=true;\

                   }\

                   if ((nexti>=N)\

                       ||(nexti<0)\

                       ||(nextj>=N)\

                       ||(nextj<0)\

                       ||(map[nexti][nextj]==’#’))\

                      answer++;\

           }

           #define bfs_f(fi,fj)\

           if (!inq[fi][fj])\

           {\

              q.push(make_pair(fi,fj));\

              inq[fi][fj]=true;\

              while (!q.empty())\

              {\

                    int gi=q.front().first,\

                        gj=q.front().second;\

                    go(1,0);\

                    go(-1,0);\

                    go(0,1);\

                    go(0,-1);\

                    q.pop();\

              }\

           }

           bfs_f(0,0);

           bfs_f(N-1,N-1);

           #undef bfs_f

           #undef go

           answer-=4;

           answer*=3*3;

           cout<<answer<<endl;

      }

      public:

      Application()

      {

                    cin>>N;

                    map.resize(N,vector<char>(N));

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

                        for (int j=0;j<N;j++)

                            cin>>map[i][j];

      }

      int run()

      {

          bfs();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

开始做了个O(n^2)的DP，但是WA#33，我改了，还是WA，重写，还是WA。无语到了极点。

后来还是用O(n)的算法做了（提示：需要用到抽屉原理）。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-20

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N;

      vector<int> a;

      public:

      Application()

      {

                    cin>>N;

                    a.resize(N);

                    for (int i=0;i<N;i++) cin>>a[i];

      }

      int run()

      {

          static const int NOTIN=-1;

          vector<int> sum(N+1);

          sum[0]=0;

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

              sum[i+1]=sum[i]+a[i];

          vector<int> counter(N,NOTIN);

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

          {

              if (counter[sum[i]%N]!=NOTIN)

              {

                 cout<<i-counter[sum[i]%N]<<endl;

                 for (int j=counter[sum[i]%N];j<i;j++)

                     cout<<a[j]<<endl;

                 break;

              }

              else counter[sum[i]%N]=i;

          }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

动态规划。朴素的O(n^2)的应该不能过。所以要优化成线性的。

如果要花C1的钱来转移，当然要尽量靠前而又不要超过L1的距离，其他同理。所以分别转移。我用了一个双端队列。具体看代码吧。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-20

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int oo=1000000000;

      int L1,L2,L3;

      int C1,C2,C3;

      int N;

      int start,end;

      vector<int> d;

      int price(int f,int t)

      {

          if (d[t]-d[f]<=L1) return C1;

          if (d[t]-d[f]<=L2) return C2;

          if (d[t]-d[f]<=L3) return C3;

          return oo;

      }

      public:

      Application()

      {

                    cin>>L1>>L2>>L3

                       >>C1>>C2>>C3

                       >>N

                       >>start>>end;

                    if (start>end)

                    {

                       int swap=start;

                       start=end;

                       end=swap;

                    }

                    start–;

                    end–;

                    d.resize(N);

                    d[0]=0;

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

                        cin>>d[i];

      }

      int run()

      {

          vector<int> f(N);

          std::deque<int> q1,q2,q3;

          f[start]=0;

          q1.push_back(start);

          q2.push_back(start);

          q3.push_back(start);

          for (int i=start+1;i<=end;i++)

          {

              f[i]=oo;

              while ((!q1.empty())&&(d[i]-d[q1.front()]>L1)) q1.pop_front();

              while ((!q2.empty())&&(d[i]-d[q2.front()]>L2)) q2.pop_front();

              while ((!q3.empty())&&(d[i]-d[q3.front()]>L3)) q3.pop_front();

              if ((!q1.empty())&&(f[i]>f[q1.front()]+price(q1.front(),i)))

                 f[i]=f[q1.front()]+price(q1.front(),i);

              if ((!q2.empty())&&(f[i]>f[q2.front()]+price(q2.front(),i)))

                 f[i]=f[q2.front()]+price(q2.front(),i);

              if ((!q3.empty())&&(f[i]>f[q3.front()]+price(q3.front(),i)))

                 f[i]=f[q3.front()]+price(q3.front(),i);

              q1.push_back(i);

              q2.push_back(i);

              q3.push_back(i);

          }

          cout<<f[end]<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

注意精度，然后看图：

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-20

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

using std::getline;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cmath>

using std::cos;

using std::acos;

//using std::M_PI;

#define M_PI (3.141592653589793238462643383279f)

#include <cassert>

//using std::assert;

#include <iomanip>

 

class Application

{

      double sx,sy,ix,iy;

      void get(string& s,double& d)

      {

           if (s.substr(0,4)==“and “) s.erase(0,4);

           stringstream cin(s);

           d=0;

           double get;

           cin>>get;

           cin.ignore();

           d+=get;

           cin>>get;

           cin.ignore();

           d+=get/60.0;

           cin>>get;

           cin.ignore();

           d+=get/3600.0;

           char flag;

           cin>>flag;

           if (flag==’N’||flag==’E’)

           {

              d=-d;

           }

      }

      double d(double get)

      {

             if (get>0) get=-get;

             if (get>180.0) get=360.0-get;

             return get;

      }

      public:

      Application()

      {

      }

      int run()

      {

          string s;

          getline(cin,s);//Message #<n>.

          getline(cin,s);//Received at <HH>:<MM>:<SS>.

          getline(cin,s);//Current ship’s coordinates are

          getline(cin,s);//<X1>^<X2>'<X3>” <NL/SL>

          get(s,sx);

          getline(cin,s);//and <Y1>^<Y2>'<Y3>” <EL/WL>.

          get(s,sy);

          getline(cin,s);//An iceberg was noticed at

          getline(cin,s);//<A1>^<A2>'<A3>” <NL/SL>

          get(s,ix);

          getline(cin,s);//and <B1>^<B2>'<B3>” <EL/WL>.

          get(s,iy);

          getline(cin,s);//===

         

          sx=sx/180.0*M_PI;

          sy=sy/180.0*M_PI;

          ix=ix/180.0*M_PI;

          iy=iy/180.0*M_PI;

         

          const double R=(6875*0.5);

          double d=R*acos(sin(sx)*sin(ix)+cos(sx)*cos(ix)*cos(sy-iy));

          cout<<“The distance to the iceberg: “

              <<std::setiosflags(std::ios::fixed)

              <<std::setprecision(2)

              <<d

              <<” miles.”<<endl;

          string stream;

          int get;

          stringstream scout(stream);

          scout<<std::setiosflags(std::ios::fixed)

               <<std::setprecision(2)

               <<d;

          stringstream scin(scout.str());

          scin>>get;

          if (get<100) cout<<“DANGER!”<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}