ZOJ 2278 Fight for Food

2745991 2008-02-07 15:05:00 Accepted 2278 C++ 00:00.68 1708K C.D.

相当出色的DP优化题。

类似于最大不下降子序列,一般有O(N2)的简单算法。但N>30000,故需要优化。原先的算法中,设F(i)= 到第i只老鼠时捕捉到的最大数目,F(i)= max(F(j)+1),j从1到i-1,假如在时限内能从第i到第j只老鼠出现的方格。这里可以预先使用BFS,用time[rati.i][rati.j][ratj.i][ratj.j]来记录从i到j的最小时间,并加以判断。

为了优化时间,首先进行预处理,把不可能捕捉到的老鼠删除,把从每一点访问所有点至少需要的时间maxtime[rati.i][rati.j]记录下来。

然后把老鼠出现的时间排序。当j从1到i-1访问的时候,可以看到有一些老鼠和当前i的时间相差太多,必然可以访问。这样只要把这些老鼠的最大值+1即可。这些老鼠是:

设老鼠j到老鼠i的时间大于i访问所有点的最大时间maxtime。那么,对于k<j,也必然大于maxtime。

这样就成功剪去大部分时间。

WA了无数遍,终于发现漏了一种不可能捕捉到老鼠的状况。鼠年做鼠题,祝自己新年快乐。

/*
    作者:    Crux.D
    日期:    2008-2-11
    描述:    动态规划的优化
*/



#include 
<iostream>
#include 
<string>
#include 
<algorithm>
using namespace std;

#define check(x, y) (x >= 0 && y >= 0 && x < N && y < M && map[x][y] == 0)

int N, M, P, map[10][10], dist[10][10][10][10], max_time[10][10], opt[30010], f[30010];
int dir[4][2=
{
    
01 }0-1 }10 }- 10 }
}
;  

typedef 
struct
{
    
int i, j, t;
}
 Rat;
Rat r[
50001];
Rat cx;
Rat q[
101];
//保存老鼠出现的队列

bool cmp ( const Rat &a, const Rat &b )
{
    
return a.t < b.t;
}


void init ();
int dp ();
void BFS ( intint );

int main ()
{
    
//freopen ( "in.txt", "r", stdin );
    while ( scanf ( "%d %d"&N, &M ) != EOF )
    
{
        init ();
        
//pt ();
        printf ( "%d\n", dp () );
    }

    
return 0;
}


void init ()
{
    
int i, j;
    
char ch[11];
    memset ( dist, 
0xffsizeof ( dist ) );
    memset ( max_time, 
0x00sizeof ( max_time ) );
    memset ( map, 
0x00sizeof  ( map ) );
    gets ( ch );
    
for ( i = 0; i < N; i ++ )
    
{
        gets ( ch );
        
for ( j = 0; j < M; j ++ )
        
{
            
if ( ch[j] == 'L' )
            
{
                cx.i 
= i, cx.j = j;
            }

            
if ( ch[j] == '#' )
            
{
                map[i][j] 
= 1;
            }

        }

    }

    BFS ( cx.i, cx.j );
    
for ( i = 0; i < N; i ++ )
    
{
        
for ( j = 0; j < M; j ++ )
        
{
            
if ( dist[cx.i][cx.j][i][j] > 0 )
            
{
                BFS ( i, j );
            }

        }

    }

   
    r[
0].i = cx.i, r[0].j = cx.j, r[0].t = 0;
    
for ( scanf ( "%d"&j ), i = 0, P = 0; i < j; i ++ )
    
{
        P 
++;
        scanf ( 
"%d%d%d"&r[P].i, &r[P].j, &r[P].t );
        r[P].i 
--, r[P].j --;
        
if ( dist[cx.i][cx.j][r[P].i][r[P].j] < 0 )
        
{
            P 
--;
        }

        
else if ( r[P].t < dist[cx.i][cx.j][r[P].i][r[P].j] )
        
{
            P 
--;
        }

    }
    
    sort ( r, r 
+ P + 1, cmp );
}


void BFS ( int i, int j )
{
    
int op, ed, ii, jj, k;
    
for ( op = -1, ed = 0, q[0].i = i, q[0].j = j, dist[i][j][i][j] = 0; op ++ < ed; )
    
{
        
for ( k = 0; k < 4; k ++ )
        
{
            ii 
= q[op].i + dir[k][0], jj = q[op].j + dir[k][1];
            
if ( check ( ii, jj ) && dist[i][j][ii][jj] < 0 )
            
{
                q[
++ ed].i = ii; q[ed].j = jj;
                dist[i][j][ii][jj] 
= dist[i][j][q[op].i][q[op].j] + 1;
            }

        }

    }

    max_time[i][j] 
= dist[i][j][q[ed].i][q[ed].j];
}


int dp ()
{
    
int i, j;    
    
for ( i = 1, f[0= opt[0= 0; i <= P; i ++ )
    
{
        f[i] 
= 0;
        
//if ( r[i].t >= dist[cx.i][cx.j][r[i].i][r[i].j] )  //prune
        {
            
for ( j = i - 1; j >= 0 && r[i].t - r[j].t < max_time[r[i].i][r[i].j]; j -- )    //prune
            {
                
if ( r[i].t - r[j].t >= dist[r[i].i][r[i].j][r[j].i][r[j].j] && f[i] < f[j] + 1 )
                
{
                    f[i] 
= f[j] + 1;
                }

            }

            
if ( j >= 0 && f[i] < opt[j] + 1 )
            
{
                f[i] 
= opt[j] + 1;
            }

        }
    
        opt[i] 
= ( opt[i - 1> f[i] ? opt[i - 1] : f[i] );
    }

    
return opt[P];
}







posted on 2008-02-07 15:30 杜仲当归 阅读(116) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。

导航

<2008年2月>
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜