URAL1037[Memory management]

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


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();


}


 


 

URAL1036[Lucky tickets]

无聊的递推。


方程:


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()-11;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();


}


 


 

URAL1035[Cross-stitch]

唉,不好说,都是看了题解做的。然后黑书上有讲,自己看吧。(刘汝佳的黑书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();


}


 


 

URAL1034[Queens in peaceful positions]

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


然后,在对角线判断一下就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();


}


 


 

URAL1033[Labyrinth]

水题,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();


}


 


 

URAL1032[Find a multiple]

开始做了个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();


}


 


 

URAL1031[Railway tickets]

动态规划。朴素的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();


}


 


 

URAL1030[Titanic]

注意精度,然后看图:


URAL1030[Titanic] - 天之骄子 - 天之骄子的家


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();


}


 


 

URAL1029[Ministry]

动态规划。(又见VIJOS1139)


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-20


DESCRIPTION:


VIJOS P1139


*/


#include <iostream>


using namespace std;


 


int F[1024];


int room[1024][1024];


int level[1024][1024];


int out[1024*1024];


int m,n;


 


int main()


{


    cin>>m>>n;


   


    for (int i=m;i>=1;i–)


    {


            int p[1024];


            for (int j=1;j<=n;j++)


            {


                cin>>p[j];


                F[j]+=p[j];


                room[i][j]=j;


                level[i][j]=i+1;


            }


            for (int j=2;j<=n;j++)


                if (F[j]>F[j-1]+p[j])


                {


                   F[j]=F[j-1]+p[j];


                   room[i][j]=j-1;


                   level[i][j]=i;


                }


            for (int j=n-1;j>=1;j–)


                if (F[j]>F[j+1]+p[j])


                {


                   F[j]=F[j+1]+p[j];


                   room[i][j]=j+1;


                   level[i][j]=i;


                }


    }


   


    int n1=1;


    for (int i=n;i>1;i–)


        if (F[i]<F[n1])


           n1=i;


    int k=0;


    for (int m1=1;m1!=m+1😉


    {


        out[k++]=n1;


        int m2=level[m1][n1];


        int n2=room[m1][n1];


        m1=m2;


        n1=n2;


    }


    for (int i=k-1;i>=0;i–)


        cout<<out[i]<<char(i?’ ‘:’\n’);


    //while (cin.get());


    return 0;


}


 

开学了[2010年3月14日]

其实已经开学有三周了,可是才发觉已经开学了。走在校园里,看到同学们往来穿梭,看到篮球场的优美的抛物线,才发觉,真的,已经开学三周了。
开学后的第一周,是在机房里度过的。停课三天,让我失去了体会与同学重逢那种感觉的机会。每天与机器对话,虽然写的是我爱的程序,但总少了一些课堂里的那种热闹的气氛。开着的音响,放着的歌,渐渐的也会成为嘈杂的声响,把我做题的节拍打乱。是有一些想那些可爱的他与她,但竞赛,只有付出才有回报,而这付出,注定会让我失去很多东西,但,必定会让我得到快乐。
开学后的第一个星期六,是信息学奥林匹克竞赛重庆代表队选拔赛在一中举行的日子,也就是小学奥数老师所说的“养兵千日,用兵一时”的那“一时”了。和老师、同学会合后,我们一起进入了考场。内心忐忑,担心自己会想以前一样在关键的考试中考砸(小学的奥数和初中的希望杯都发挥得很差)。进入考场,我镇定了下来,喝了几口水,然后从容的看了一遍考卷。半小时后,我敲完了第一题的程序,我自信能AC(AC:即Accept,可以理解为得满分)。然后剩下的3题就顺利的做了,因为即使后面几题做得不太好,凭第1题的AC也差不多可以进队了。5小时后,考试结束。到食堂吃饭,吃不下,很激动。之后到考场外等成绩,前三题,我总分列第三,加上联赛,总分第一,但是令我失望的是老师讲第一题我0分。确定能进队后,我和同学离开了。
当天晚上,得知第一题数据出错,之前的分数不对,第一题,我AC了!
第二周,我完全沉浸在这胜利的的喜悦之中。从老师那里得知的数据,我看到了选拔赛的分数,我236分居第一,加上联赛分数总分456领先第二名100多分。很高兴,然后又是忙碌的投入竞赛事业中去了。
第三周,竞赛班的同学们陪着我度过了我的第十七个生日,我感觉自己很快乐。
三周,很快就过去了,却感觉自己脑中满是竞赛,不曾发觉已经开学很久了,已经是高二下期了。开学了,不能再像放假时那么自由的玩了,也不能像停课时那样自由。开学了,忙碌的学习未完待续。