苍月流影

2745991

2008-02-07 15:05:00

Accepted

2278

C++

00:00.68

1708K

C.D.

相当出色的DP优化题。

类似于最大不下降子序列，一般有O(N²)的简单算法。但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];
}