首页 > ACM题库 > HDU-杭电 > HDU 4739-Zhuge Liang’s Mines-动态规划-[解题报告]HOJ
2015
09-17

HDU 4739-Zhuge Liang’s Mines-动态规划-[解题报告]HOJ

Zhuge Liang’s Mines

问题描述 :

In the ancient three kingdom period, Zhuge Liang was the most famous and smartest military leader. His enemy was Shima Yi, who always looked stupid when fighting against Zhuge Liang. But it was Shima Yi who laughed to the end.

Once, Zhuge Liang sent the arrogant Ma Shu to defend Jie Ting, a very important fortress. Because Ma Shu is the son of Zhuge Liang’s good friend Ma liang, even Liu Bei, the Ex. king, had warned Zhuge Liang that Ma Shu was always bragging and couldn’t be used, Zhuge Liang wouldn’t listen. Shima Yi defeated Ma Shu and took Jie Ting. Zhuge Liang had to kill Ma Shu and retreated. To avoid Shima Yi’s chasing, Zhuge Liang put some mines on the only road. Zhuge Liang deployed the mines in a Bagua pattern which made the mines very hard to remove. If you try to remove a single mine, no matter what you do ,it will explode. Ma Shu’s son betrayed Zhuge Liang , he found Shima Yi, and told Shima Yi the only way to remove the mines: If you remove four mines which form the four vertexes of a square at the same time, the removal will be success. In fact, Shima Yi was not stupid. He removed as many mines as possible. Can you figure out how many mines he removed at that time?

The mine field can be considered as a the Cartesian coordinate system. Every mine had its coordinates. To simplify the problem, please only consider the squares which are parallel to the coordinate axes.

输入:

There are no more than 15 test cases.
In each test case:

The first line is an integer N, meaning that there are N mines( 0 < N <= 20 ).

Next N lines describes the coordinates of N mines. Each line contains two integers X and Y, meaning that there is a mine at position (X,Y). ( 0 <= X,Y <= 100)

The input ends with N = -1.

输出:

There are no more than 15 test cases.
In each test case:

The first line is an integer N, meaning that there are N mines( 0 < N <= 20 ).

Next N lines describes the coordinates of N mines. Each line contains two integers X and Y, meaning that there is a mine at position (X,Y). ( 0 <= X,Y <= 100)

The input ends with N = -1.

样例输入:

3
1 1
0 0
2 2
8
0 0
1 0
2 0
0 1
1 1
2 1
10 1
10 0
-1

样例输出:

0
4

九野的博客,转载请注明出处:http://blog.csdn.net/acmmmm/article/details/11711707

求所有可能围成的正方形,借个代码

#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstdio>
#include <math.h>
#include <cstdlib>
#include <string.h>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define LL long long
#define PI acos(-1.0)
#define N 5100
#define M 1148576
#define inf 1000000000

struct node {
    int a, b, c, d;
    void set (int _a, int _b, int _c, int _d) {
        a = _a; b = _b; c = _c; d = _d;
    }
}pe[N];
struct point {
    int x, y;
    void set () {
        scanf ("%d%d", &x, &y);
    }
}p[30];
int cnt;
int cmp (point a, point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
int dp[M];
int dfs (int s) {
    if (dp[s] != -1) return dp[s];
    int Max = 0;
    for (int i = 0; i < cnt; ++i) {
        if ((s&(1<<pe[i].a)) + (s&(1<<pe[i].b))+(s&(1<<pe[i].c)) + (s&(1<<pe[i].d)) == 0) {
            int si = s + (1<<pe[i].a) + (1<<pe[i].b) + (1<<pe[i].c) + (1<<pe[i].d);
            Max = max (Max, dfs (si) + 4);
        }
    }
    return dp[s]= Max;
}
int main () {
    int n;
    while (scanf ("%d", &n), n != -1) {
        for (int i = 0; i < n; ++i) {
            p[i].set();
        }
        cnt = 0;
        sort (p, p + n, cmp);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (p[i].x != p[j].x) break;
                for (int ii = j + 1;  ii < n; ++ii) {
                    for (int jj = ii + 1; jj < n; ++jj) {
                        if (p[ii].x != p[jj].x) continue;
                        if (p[i].y == p[ii].y && p[j].y == p[jj].y && p[j].y - p[i].y == p[ii].x - p[i].x) {
                            pe[cnt].set (i, j, ii, jj);
                        //    cout << i << ' ' << j << ' ' << ii << ' ' << jj << endl;
                            cnt++;
                        }
                    }
                }
            }
        }
        memset (dp, -1, sizeof (dp));
        printf ("%d\n", dfs (0));
    }
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acmmmm/article/details/11711707