首页 > 代码库 > bzoj 1193 贪心

bzoj 1193 贪心

2024-07-03 15:27:38   227人阅读

　　如果两点的曼哈顿距离在一定范围内时我们直接暴力搜索就可以得到答案，那么开始贪心的跳，判断两点横纵坐标的差值，差值大的方向条2，小的条1，不断做，直到曼哈顿距离较小时可以暴力求解。

　　备注：开始想的是确定一点周围跳到这个点的答案，然后再枚举周围的点，判断这个点和另一个点的曼哈顿距离，如果能被3整除就说明之前可以一直跳过来，不知道怎么不对。

/**************************************************************
    Problem: 1193
    User: BLADEVIL
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:4800 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#define abs(x) (x>0?x:-x)
#define maxn 1010
 
using namespace std;
 
int x1,x2,y1,y2,x,y;
int dis[maxn][maxn],quex[maxn],quey[maxn];
int go[10][2];
int ans;
 
int main() {
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    x=x1-x2; x=abs(x); y=y1-y2; y=abs(y);
    while ((x>=10)||(y>=10)) {
        if (x>y) x-=2,y-=1; else x-=1,y-=2;
        ans++;
        x=abs(x); y=abs(y);
    }
    //printf("%d\n",ans);
    //printf("%d %d\n",x,y);
    x++; y++;
    dis[1][1]=0;
    dis[1][2]=3;
    dis[1][3]=2;
    dis[1][4]=3;
    dis[1][5]=2;
    dis[1][6]=3;
    dis[1][7]=4;
    dis[1][8]=5;
    dis[1][9]=4;
    dis[1][10]=5;
    dis[1][11]=6;
    dis[2][1]=3;
    dis[2][2]=2;
    dis[2][3]=1;
    dis[2][4]=2;
    dis[2][5]=3;
    dis[2][6]=4;
    dis[2][7]=3;
    dis[2][8]=4;
    dis[2][9]=5;
    dis[2][10]=6;
    dis[2][11]=5;
    dis[3][1]=2;
    dis[3][2]=1;
    dis[3][3]=4;
    dis[3][4]=3;
    dis[3][5]=2;
    dis[3][6]=3;
    dis[3][7]=4;
    dis[3][8]=5;
    dis[3][9]=4;
    dis[3][10]=5;
    dis[3][11]=6;
    dis[4][1]=3;
    dis[4][2]=2;
    dis[4][3]=3;
    dis[4][4]=2;
    dis[4][5]=3;
    dis[4][6]=4;
    dis[4][7]=3;
    dis[4][8]=4;
    dis[4][9]=5;
    dis[4][10]=6;
    dis[4][11]=5;
    dis[5][1]=2;
    dis[5][2]=3;
    dis[5][3]=2;
    dis[5][4]=3;
    dis[5][5]=4;
    dis[5][6]=3;
    dis[5][7]=4;
    dis[5][8]=5;
    dis[5][9]=4;
    dis[5][10]=5;
    dis[5][11]=6;
    dis[6][1]=3;
    dis[6][2]=4;
    dis[6][3]=3;
    dis[6][4]=4;
    dis[6][5]=3;
    dis[6][6]=4;
    dis[6][7]=5;
    dis[6][8]=4;
    dis[6][9]=5;
    dis[6][10]=6;
    dis[6][11]=5;
    dis[7][1]=4;
    dis[7][2]=3;
    dis[7][3]=4;
    dis[7][4]=3;
    dis[7][5]=4;
    dis[7][6]=5;
    dis[7][7]=4;
    dis[7][8]=5;
    dis[7][9]=6;
    dis[7][10]=5;
    dis[7][11]=6;
    dis[8][1]=5;
    dis[8][2]=4;
    dis[8][3]=5;
    dis[8][4]=4;
    dis[8][5]=5;
    dis[8][6]=4;
    dis[8][7]=5;
    dis[8][8]=6;
    dis[8][9]=5;
    dis[8][10]=6;
    dis[8][11]=7;
    dis[9][1]=4;
    dis[9][2]=5;
    dis[9][3]=4;
    dis[9][4]=5;
    dis[9][5]=4;
    dis[9][6]=5;
    dis[9][7]=6;
    dis[9][8]=5;
    dis[9][9]=6;
    dis[9][10]=7;
    dis[9][11]=6;
    dis[10][1]=5;
    dis[10][2]=6;
    dis[10][3]=5;
    dis[10][4]=6;
    dis[10][5]=5;
    dis[10][6]=6;
    dis[10][7]=5;
    dis[10][8]=6;
    dis[10][9]=7;
    dis[10][10]=6;
    dis[10][11]=7;
    dis[11][1]=6;
    dis[11][2]=5;
    dis[11][3]=6;
    dis[11][4]=5;
    dis[11][5]=6;
    dis[11][6]=5;
    dis[11][7]=6;
    dis[11][8]=7;
    dis[11][9]=6;
    dis[11][10]=7;
    dis[11][11]=8;
    printf("%d\n",ans+dis[x][y]);
    return 0;
}

 


联系
我们