Posted on 2009-12-11 19:59
rikisand 阅读(206)
评论(0) 编辑 收藏 引用 所属分类:
Topcoder 、
Algorithm
一直没写，补上上次的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;
}