51NOD 占领资源 - dblank

51NOD 占领资源

1487 占领资源
题目来源: TopCoder
基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 收藏 关注
有一个矩形区域被划分为N行M列的网格,每个格子里有一定数量的资源并记录在矩阵val中,坐标(x,y)位置上资源量为valx,其val中每个元素的值为0~9的整数。如果你在某个网格(a,b)上造一座保护塔,那么你可以占领K个网格中的资源,这K个格子分别是(a+dx[1],b+dy[1]),(a+dx[2],b+dy[2]),...,(a+dx[K],b+dy[K]),注意(a,b)这格本身可能未必会被占领。现在你能建造不超过2个塔,问最多能占领多少资源?一个网格被多个塔占领时其资源只计算一次。另外如果计算的位置(a+dx[i],b+dy[i])在网格外,则不贡献任何资源。

Input
多组测试数据,第一行一个整数T,表示测试数据数量,1<=T<=5
每组测试数据有相同的结构构成:
每组数据第一行三个整数N,M,K,其中2<=N,M<=100,1<=K<=10。
之后会有N行,每行M个元素,表示val矩阵。每个元素为0~9,占一个字符,元素间没空格。
再接下来有K行,每行两个整数dx[i]与dy[i],其中-(N-1)<=dx[i]<=N-1,-(M-1)<=dy[i]<=(M-1).
Output
每组数据一行输出,即可占领的最大资源总量。
Input示例
3
2 2 2
11
11
0 0
0 1
2 2 2
11
11
0 0
1 1
2 2 1
15
61
0 0
Output示例
4
3
11

思路:如果直接暴力枚举的话肯定是要超时的,我们可以这样子优化,对于两个点来说,要么没有交集,要么有交集。对于没有交集的点点来说,我们可以枚举第一个点,然后在和他没有交集的点里面选一个最大的,这个地方我们可以事先找到和他有交集的,并且把二维的坐标转变为一维的,利用rmq查找。有交集的点的话,直接暴力在有交集的点里面找到最大收益就好了。复杂度O(nmk*k)

#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl '\n'
#define x first
#define y second
using namespace std;

const int N = 100 + 10, inf = 0x3f3f3f3f;

int path[N][N], vis[N][N], val[N*N];
int dx[N], dy[N], n, m, k, dp[N*N][20], lim[N*N];
int ID(int x, int y)
{
    return (x-1) * m + y;
}

bool yes(int x, int y)
{
    if(x<1 || x>n || y<1 || y>m)
        return false;
    return true;
}
void RmqInit(int len)
{
    for(int i = 1; i<=len; i++)
    {
        dp[i][0] = val[i];
    }
    for(int j = 1; (1<<j)<=len; j++)
    {
        for(int i = 1; i+(1<<j)-1<=len; i++)
            dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
    }
}
int query(int l, int r)
{
    int now = 0;
    while((1<<(now+1)) <= r-l+1)
        now++;
    return max(dp[l][now], dp[r-(1<<now)+1][now]);
}
int solve()
{
    int res = 0;
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=m; j++)
        {
            int nx, ny;
            cnt = 0;
            for(int r = 1; r <= k; r++)
            {
                nx = i + dx[r], ny = j + dy[r];
                if(!yes(nx, ny))
                    continue;
                vis[nx][ny] = ID(i, j);
                for(int t = 1; t<=k; t++)
                {
                    int nnx = nx - dx[t], nny = ny - dy[t];
                    if(!yes(nnx, nny))
                        continue;
                    lim[cnt++] = ID(nnx, nny);
                }
            }

            lim[cnt++] = 0;
            lim[cnt++] = n*m+1;
            sort(lim, lim+cnt);
            cnt = (int)(unique(lim, lim+cnt) - lim);
            for(int r = 0; r<cnt-1; r++)
            {
                if(lim[r]+1<=lim[r+1]-1)
                    res = max(res, query(lim[r]+1, lim[r+1]-1) + val[ ID(i, j) ]);
            }
            for(int r = 1; r<cnt-1; r++)
            {
                int nx = (lim[r]-1)/m + 1, ny = (lim[r]-1)%m + 1, sum = val[lim[r]];
                for(int t = 1; t<=k; t++)
                {
                    int nnx = nx + dx[t], nny = ny + dy[t];
                    if(!yes(nnx, nny))
                        continue;
                    if(vis[nnx][nny] == ID(i, j))
                        sum -= path[nnx][nny];
                }
                res = max(res, sum + val[ ID(i, j) ]);
            }
        }
    return res;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        char s[N];
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i<=n; i++)
        {
            scanf("%s", s+1);
            for(int j = 1; j<=m; j++)
                path[i][j] = s[j] - '0';
        }
        for(int i = 1; i<=k; i++)
            scanf("%d%d", &dx[i], &dy[i]);
        int nx, ny;
        for(int i = 1; i<=n; i++)
            for(int j = 1; j<=m; j++)
            {
                int sum = 0;
                for(int r = 1; r<=k; r++)
                {
                    nx = i + dx[r], ny = j + dy[r];
                    if(yes(nx, ny))
                        sum += path[nx][ny];
                }
                val[ ID(i, j) ] = sum;
            }
        RmqInit(n*m);
        printf("%d\n", solve());
    }
    return 0;
}

相关文章

发表新评论