Topcoer SRM 453.5

Posted on 2009-12-11 19:59 rikisand 阅读(206) 评论(0)  编辑 收藏 引用 所属分类: TopcoderAlgorithm

一直没写,补上上次的srm~

250pt

500pt 队列BFS

Code Snippet
template<class T> void getMin(T& a,T b){if(b<a)a=b;}
template<class T> void getMax(T& a,T b){if(b>a)a=b;}
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define inf 98765432
int mp[55][55];
struct node{
    int c;
    int r;
    int value;
    node(int rr,int cc,int vv):r(rr),c(cc),value(vv){}
};
class MazeMaker
{
        public:
        int longestPath(vector <string> maze, int sRow, int sCol, vector <int> mRow, vector <int> mCol)
        {
                int R=maze.size();
                int C=maze[0].size();
                REP(i,R)REP(j,C)mp[i][j]=inf;
                deque<node> q;
                q.push_back(node(sRow,sCol,0));
                while(!q.empty()){
                    node now=q.front();
                    q.pop_front();
                    int r=now.r;int c=now.c ;int v=now.value;
                    if( mp[r][c]!=inf)continue;
                    mp[r][c]=v;
                    for(int i=0;i<mRow.size();i++){
                        int nr=r+mRow[i];int nc=c+mCol[i];
                        if(nr<0||nr>=R||nc<0||nc>=C||mp[nr][nc]!=inf||maze[nr][nc]=='X')continue;
                        q.push_back(node(nr,nc,v+1));
                    }
                }
                int res=-1;
                REP(i,R)REP(j,C){
                    if(maze[i][j]=='.'){
                        if(mp[i][j] == inf)return -1;
                        if(mp[i][j]>res)res=mp[i][j];
                    }
                }
                return res;
        }

DFS也可以

VS mp;
VI mR,mC;int N,R,C; 
int used[55][55];
void DFS(int r,int c,int len){
    REP(i,mR.size()){
        int nr=r+mR[i];int nc=c+mC[i];
        if(nr<0||nr>=R||nc<0||nc>=C||mp[nr][nc]=='X')continue;
        if(used[nr][nc]<=len+1)continue;
        used[nr][nc]=len+1;
        DFS(nr,nc,len+1);
    }
}
class MazeMaker
{
        public:
        int longestPath(vector <string> maze, int sRow, int sCol, vector <int> moveRow, vector <int> moveCol)
        {
                mR=moveRow;mC=moveCol;mp=maze;
                R=maze.size();C=maze[0].size();
                REP(i,R)REP(j,C)used[i][j]=inf;
                used[sRow][sCol]=0;
                DFS(sRow,sCol,0);
                int res=-1;
                REP(i,R)REP(j,C){
                    if(mp[i][j]=='.'){
                        if(used[i][j]==inf)return -1;
                        if(used[i][j]>res)res=used[i][j];
                    }
                }
                return res;
        }

1000pt

实际为求从中取出K个数字,连续两个间的序号差不能大于maxDist 求能够求得的最大乘积

由于有负数的存在,最大数字的取得可能是最大的乘以最大的,或者最大的乘以最小的(正 负相乘)

因此要保存到每一个数为止,作为第k个数,取得的最大最小值,dp求解之

 

Code Snippet
typedef long long int64;   

template<class T> void getMin(T& a,T b){if(b<a)a=b;}
template<class T> void getMax(T& a,T b){if(b>a)a=b;}
#define REP(i, n) for (int i = 0; i < (n); ++i)
int64 dp[55][55][2];//µÚ¼¸¸ö£¬ÓÃÁ˼¸¸ö£¬Õý»¹ÊǸº;
#define inf 133
class TheProduct
{
        public:
        long long maxProduct(vector <int> infm, int _K, int maxD)
        {
            int N = infm.size();
            memset(dp,-1,sizeof(-1));
            REP(i,N)REP(j,51)REP(c,2)dp[i][j][c]=inf;
            REP(i,N)  dp[i][0][0]=dp[i][0][1]=(int64)infm[i];
            
            for(int i=0;i<N;i++)
                for(int j=i-1;i-j<=maxD && j>=0;j--)
                    for(int z=0;z<_K;z++){
                        if(dp[j][z][0]!=inf){
                            if(dp[i][z+1][0]==inf||dp[j][z][0]*infm[i]<dp[i][z+1][0])dp[i][z+1][0]=dp[j][z][0]*infm[i];
                            if(dp[i][z+1][1]==inf||dp[j][z][0]*infm[i]>dp[i][z+1][1])dp[i][z+1][1]=dp[j][z][0]*infm[i];
                        }
                        if(dp[j][z][1]!=inf){
                            if(dp[i][z+1][0]==inf||dp[j][z][1]*infm[i]<dp[i][z+1][0])dp[i][z+1][0]=dp[j][z][1]*infm[i];
                            if(dp[i][z+1][1]==inf||dp[j][z][1]*infm[i]>dp[i][z+1][1])dp[i][z+1][1]=dp[j][z][1]*infm[i];
                        }
                    }
            int64 res=-(1LL<<63);
            REP(i,N){
                if(dp[i][_K-1][1]!=inf)
                 getMax(res,dp[i][_K-1][1]);    
            }
            return res;
        }

 

 

 

 

 

 

 

 

 

 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理