2745991 2008-02-07 15:05:00 Accepted 2278 C++ 00:00.68 1708K C.D. 感谢W111（WCY）同学的解题报告。 相当出色的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] ={    { 0, 1 }, { 0, -1 }, { 1, 0 }, { - 1, 0 }};  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 ( int, int );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, 0xff, sizeof ( dist ) );    memset ( max_time, 0x00, sizeof ( max_time ) );    memset ( map, 0x00, sizeof  ( 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];}

评论