ZOJ 1107 FatMouse and Cheese(DP)

ZOJ 1107 FatMouse and Cheese

给出一个地图,每个点上有相应数量的cheese,从(0,0)开始,每到一个格子就把这个格子里的cheese吃光,每走一步方向只能是上下左右,每一步最多的格子数为k,每一步之后的一格所包含的cheese数量要比之前一格多…怎样才能使得所得的cheese数最多呢,输出最多的cheese数.

刚开始我想的搜索,但是无门.但是看题之前已经知道是dp了,就一直往那方面想,一开始就想到了从cheese最大点开始,把他相应范围内的最大数更新一下,也就是dp[i][j] = map[i][j] + (与i,j在合法范围内dp[*][*]最大值),dp[i][j]表示从(i,j)开始所能得到的最多cheese。但是想想实现起来比较麻烦。昨天晚上睡觉上微博的时候，突然想到把这些点按照cheese数排列，然后从前往后进行dp，相当于LIS，只不过中间的限制条件比较多。按照这个思路，我写出代码，并且ac掉：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>

using namespace std;
#define MAX 100
struct node
{
    int x;
    int y;
    int a;//cheese数量
}temp;
int cmp(const void * a,const void *b )
{
    int aa = ( (struct node*)a )->a;
    int bb = ( (struct node*)b )->a;
    return bb-aa;
}
int ok(node *a,int i,int j,int k)
{
    if( a[i].x==a[j].x && (a[i].y-a[j].y <= k &&a[i].y-a[j].y >= -k ) )
        return 1;
    if( a[i].y==a[j].y && (a[i].x-a[j].x <= k &&a[i].x-a[j].x >= -k ) )
        return 1;
    return 0;
}
int main(void)
{
    node map[MAX*MAX + 10];
    int   dp[MAX*MAX + 10];
    int i,j,count,k,n,biao,max;
    while( cin >> n >> k )
    {
        if( n == -1 && k == -1 ) break;
        count = n*n;
        for( i = 0; i < n; i++ )
            for( j = 0; j < n; j++ )
            {
                cin >> map[i*n+j].a;
                map[i*n+j].x = i;
                map[i*n+j].y = j;
            }

        qsort( map,count,sizeof(node),cmp );
        dp[0] = map[0].a;
        for( i = 1; i < count; i++ )
        {
            max = 0;
            for( j = 0; j < i; j++ )
                if( map[j].a > map[i].a &&
                    ok(map,i,j,k) &&
                    dp[j] > max )
                    max = dp[j];
            dp[i] = max + map[i].a;
        }
        for( i=0; i <count; i++ )
            if( map[i].x == 0 && map[i].y == 0)
            {cout<<dp[i]<<endl;break;}
    }
    return 0;
}

但是呢，cheese数比(0,0)小的点对于结果没有影响，所以可以把这些点去掉，再来一次：

时间减半：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>

using namespace std;
#define MAX 100
struct node
{
    int x;
    int y;
    int a;//cheese数量
}temp;
int cmp(const void * a,const void *b )
{
    int aa = ( (struct node*)a )->a;
    int bb = ( (struct node*)b )->a;
    return bb-aa;
}
int ok(node *a,int i,int j,int k)
{
    if( a[i].x==a[j].x && (a[i].y-a[j].y <= k &&a[i].y-a[j].y >= -k ) )
        return 1;
    if( a[i].y==a[j].y && (a[i].x-a[j].x <= k &&a[i].x-a[j].x >= -k ) )
        return 1;
    return 0;
}
int main(void)
{
    node map[MAX*MAX + 10];
    int   dp[MAX*MAX + 10];
    int i,j,count,k,n,biao,max;
    while( cin >> n >> k )
    {
        if( n == -1 && k == -1 ) break;
        count = 0;
        cin >> temp.a ;
        temp.x = 0;temp.y = 0;
        biao = temp.a;
        map[ count++ ] = temp;
        for( i = 0; i < n; i++ )
            for( j = (i==0?1:0); j < n; j++ )
            {
                cin >> temp.a;
                if( temp.a <= biao ) continue;
                temp.x = i;temp.y = j;
                map[ count++ ] = temp;
            }

        qsort( map,count,sizeof(node),cmp );
        for( i = 0; i < count; i++ )
            dp[i] = map[i].a;
        for( i = 1; i < count; i++ )
        {
            max = 0;
            for( j = 0; j < i; j++ )
                if( ok(map,i,j,k) && dp[j] > max && map[i].a < map[j].a)
                    max = dp[j];
            dp[i] += max;
        }
        cout << dp[count-1] << endl;
    }
    return 0;
}

然后我看了看status版，发现我的效率非常低，别人的都是100ms以下的，我想了想，能影响一个点值的因素只有他上下左右距离k以内的点，所以再建立一个图保存cheese值，ac之后发现有了大大的提高，时间剪了不少：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define MAX 100
using namespace std;
struct node
{
    int x;
    int y;
    int a;//cheese数量
}temp;
int cmp(const void * a,const void *b )
{
    return ( (struct node*)b )->a - ( (struct node*)a )->a;
}
int main(void)
{
    node map[MAX*MAX + 10];
    int dp[MAX+10][MAX+10];
    int mat[MAX+10][MAX+10];
    int i,j,m,count,k,n,biao,max;
    int xx,yy;
    int dir[4][2] = {1,0,0,1,0,-1,-1,0};
    while( cin >> n >> k )
    {
        if( n == -1 && k == -1 ) break;
        count = n*n;
        for( i = 0; i < n; i++ )
            for( j = 0; j < n; j++ )
            {
                cin >> map[i*n+j].a;
                map[i*n+j].x = i;
                map[i*n+j].y = j;
                dp[i][j] = map[i*n+j].a;
                mat[i][j] = dp[i][j];
            }

        qsort( map,count,sizeof(node),cmp );
        for( i = 0; i < count; i++ )
        {
            max = 0;
            for( j = 0; j < 4; j++ )//四个方向
            {
                xx = map[i].x;
                yy = map[i].y;
                for( m = 1; m <= k; m++ )
                {
                    xx += dir[j][0];
                    yy += dir[j][1];
                    if( xx >= 0 && xx < n &&
                        yy >= 0 && yy < n &&
                        mat[xx][yy] > map[i].a &&
                        dp[ xx ][ yy ] > max )
                        max = dp[ xx ][ yy ] ;
                    if(!( xx >= 0 && xx < n &&
                        yy >= 0 && yy < n ))
                        break;
                }
            }
            dp[ map[i].x ][ map[i].y ] += max;
        }
        cout << dp[0][0] << endl;
    }
    return 0;
}

经过这三个ac之后我非常高兴，改称c语言之后80ms过了。之前我认为dp是一座大山，现在感觉慢慢开窍了，以后要做做这类题，感觉很有成就感，继续加油喽~