2015
04-13

# A Hard Journey

ChenX was taken away by the arch devil, so the sharp shooter Brother Zheng was going to rescue him. The enemy’s army was distributed in an N * N grid, and each grid also can be divided in M * M small grids.

Brother Zheng’s army has two kinds of attack form : from top to bottom, or from left to right. The weapon they use is Break-Cloud arrow, so each arrow will cost P fighting strength to eliminate a row or a column enemies in a big grid.

Notice that they can change the attack form at any time, and when they once change their attack form, they will use Q fighting strength.

The initial position of Brother Zheng is at the top-left corner, and ChenX was locked by arch devil at the right-bottom corner. When once make a move, Brother Zheng should eliminate all the enemies in the current big grid. If the current attack form is from top to bottom, then they can move onto the right grid of the big grid; if the current attack form is from left to right, then they can move onto the bottom grid of the big grid. The initial attack form can be either of the two.

Now Brother Zheng want to know how much the least fighting strength is so that can rescue ChenX.

For the case as the followed picture, N = 2, M = 3, P = 2, Q = 1.
Brother Zheng choices to start with the attack form: from top to bottom. It takes P * 1 fighting strength to eliminate all the enemies at grid[1][1]. Then Brother Zheng changed attack form to “from left to right” using Q fighting strength, and moved to the bottom grid[2][1]. To eliminate all the enemies, it takes P * 2 fighting strength. Then Brother Zheng changed attack form to ”from top to bottom” using Q fighting strength, and moved to the right grid[2][2], after used P * 3 fighting strength to eliminate this grid, ChenX was rescue with P * 1 + Q + P * 2 + Q + P * 3 = 14 fighting strength.

For each case, the first line contains 4 integers: N, M, P, Q(0 < N <= 20, 0 < M <= 15, 0 <= P <= 20, 0 <= Q <= 20), the next N * N blocks, each block contains M * M matrixes, rows first.

For each case, the first line contains 4 integers: N, M, P, Q(0 < N <= 20, 0 < M <= 15, 0 <= P <= 20, 0 <= Q <= 20), the next N * N blocks, each block contains M * M matrixes, rows first.

2 3 2 1
0 0 1
0 0 1
0 0 1
1 1 1
1 1 1
1 1 1
0 1 1
0 0 0
1 1 1
1 0 0
0 1 0
0 0 1
1 3 3 1
0 0 1
0 0 1
1 1 1

14
7

/**

**/

#include <iostream>
#include <cstring>

#include <cstdio>

#include <algorithm>

using
namespace std;

int cost[25][25][5];
int
dp[25][25][3];
int
g[25][25];
int
n, m, p, q;

const int N = 35;
const
int M = N * N * 6;

struct Edge
{

int v;
Edge *next;
};

int
ne;
Edge
ebuf[M];        //内存池
Edge
void
{

Edge &e = ebuf[ne++];
e.v = to;
}

int cx[N], cy[N], disx[N], disy[N];    //cx[] cy[]:顶标; disx[] disy[]层次图标号
int
nx, ny;
int
Q[N];
bool
bfs()    //bfs找层次图
{

memset(disx, 0, sizeof(disx));
memset(disy, 0, sizeof(disy));
bool flag = false;
int l = 0, r = 0;
for (int i = 1; i <= nx; i++)
if (cx[i] ==  - 1)
Q[r++] = i;
while (l < r)
{
int x = Q[l++];
for (Edge *p = head[x]; p; p = p->next)
{
int y = p->v;
if (!disy[y])
{
disy[y] = disx[x] + 1;
if (cy[y] ==  - 1)
flag = true;
else
{
disx[cy[y]] = disy[y] + 1;
Q[r++] = cy[y];
}
}
}
}
return flag;
}

bool dfs(int x)
{

for (Edge *p = head[x]; p; p = p->next)
{
int y = p->v;
if (disy[y] == disx[x] + 1)    //在层次图中增广
{
disy[y] = 0;
if (cy[y] ==  - 1 || dfs(cy[y]))
{
cx[x] = y;
cy[y] = x;
return true;
}
}
}
return false;
}

inline int HopcroftKarp()
{

memset(cx,  -1, sizeof(cx));
memset(cy,  -1, sizeof(cy));
int ret = 0;
while (bfs())
for (int i = 1; i <= nx; i++)
if (cx[i] ==  -1 && dfs(i))
ret++;
return ret;
}

int
hang[25];
int
lie[25];
void
cal_val(int g[25][25], int x, int y)
{

memset(hang, 0, sizeof(hang));
memset(lie, 0, sizeof(lie));
ne = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++)
{
if (g[i][j])
{
hang[i]++;
lie[j]++;
}
}
cost[x][y][1] = cost[x][y][2] = 0;
for (int i = 1; i <= m; i++)
{
if (hang[i]) cost[x][y][1] += p;
if (lie[i]) cost[x][y][2] += p;
}
nx = ny = m;
cost[x][y][3] = cost[x][y][4] = HopcroftKarp() * p + q;
}

const int inf = 1000000005;

inline void Min(int &a, int b)
{

if (b < a) a = b;
}

int main()
{

//freopen(“in.txt”, “r”, stdin);

while (scanf(“%d%d%d%d”, &n, &m, &p, &q) != EOF)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= m; k++)
for (int h = 1; h <= m; h++)
scanf(“%d”, &g[k][h]);
cal_val(g, i, j);
}
// dp
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 1; k <= 2; k++)
dp[i][j][k] = inf;
dp[1][1][1] = min(cost[1][1][1], cost[1][1][4]);
dp[1][1][2] = min(cost[1][1][2], cost[1][1][3]);

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (i == 1 && j == 1)
continue;
// top -> down
Min(dp[i][j][1], dp[i - 1][j][1] + cost[i][j][1]);
Min(dp[i][j][1], dp[i - 1][j][1] + cost[i][j][4] + q);
Min(dp[i][j][1], dp[i - 1][j][2] + cost[i][j][1] + q);
Min(dp[i][j][1], dp[i - 1][j][2] + cost[i][j][4] + q + q);

Min(dp[i][j][2], dp[i - 1][j][1] + cost[i][j][2] + q);
Min(dp[i][j][2], dp[i - 1][j][1] + cost[i][j][3]);
Min(dp[i][j][2], dp[i - 1][j][2] + cost[i][j][2] + q + q);
Min(dp[i][j][2], dp[i - 1][j][2] + cost[i][j][3] + q);

// left -> right
Min(dp[i][j][1], dp[i][j - 1][1] + cost[i][j][1] + q + q);
Min(dp[i][j][1], dp[i][j - 1][1] + cost[i][j][4] + q);
Min(dp[i][j][1], dp[i][j - 1][2] + cost[i][j][1] + q);
Min(dp[i][j][1], dp[i][j - 1][2] + cost[i][j][4]);

Min(dp[i][j][2], dp[i][j - 1][1] + cost[i][j][2] + q);
Min(dp[i][j][2], dp[i][j - 1][1] + cost[i][j][3] + q + q);
Min(dp[i][j][2], dp[i][j - 1][2] + cost[i][j][2]);
Min(dp[i][j][2], dp[i][j - 1][2] + cost[i][j][3] + q);
}
int ans = min(dp[n][n][1], dp[n][n][2]);
cout << ans << endl;
}
}

1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。