Posted on by jasper

poj_1009(TLE&MLE)

/*
//ACM Poj 1009
//File: 1009.cpp
//Author: Kangzj
//Mail: Kangzj@mail.bnu.edu.cn
//Date: April 29, 2009
*/
#include
#include
#include
#include
using namespace std;
struct node
{
  int pix;
  int count;
};
int main()
{
  int width,i;
  int pix;
  long len;
  ostringstream buff;
    while(cin>>width&&width!=0)
  {
    //读入图像并解码
    vectorimgin;
    while(cin>>pix>>len&&len!=0)
    {
      vectortemp(len,pix);
      imgin.insert(imgin.end(),temp.begin(),temp.end());
    }
    int height;
    int size=imgin.size();
    height=size/width;
    vectorimgout(size,0);
    for(i=0;i=start)
        {
          max=abs(imgin[pos-1]-imgin[pos]);
        }
        if((pos+1)m?max:m;
        }
        if(pos+widthm?max:m;
          if(pos+width+1m?max:m;
          }
          if(pos+width-1>=start+width)
          {
            int m=abs(imgin[pos+width-1]-imgin[pos]);
            max=max>m?max:m;
          }
        }
        if(pos-width>=0)
        {
          int m=abs(imgin[pos-width]-imgin[pos]);
          max=max>m?max:m;
          if(pos-width+1< =start-1)
          {
            int m=abs(imgin[pos-width]-imgin[pos]);
            max=max>m?max:m;
          }
          if(pos-width-1>=start-width)
          {
            int m=abs(imgin[pos-width-1]-imgin[pos]);
            max=max>m?max:m;
          }
        }
        imgout[pos]=max;
      }
    }
    //将输出图像编码
    buff< rle;
    //第一个先放进去
    node tn;
    tn.pix=imgout[0];
    tn.count=0;
    rle.push_back(tn);
    //游程编码
    for(i=0;i

虽然AC了，但其实是不合格的，时间和空间都超了，500000000的数据量没法处理，好在测试集里没有这样的数据。。。转了一篇别人做的，质量真的不错，想到了好多我根本就没去想的问题，受教了。

代码完全是按题意做的，一点也没有改进：

Leave a Reply

%d