SRM 574
XX..
.X..
XX..
....
XX..
.X..
다섯 번째 줄을 이어서 세 번째 줄을 하나로 만들 수 있다. 이것은 욕심으로 해결할 수 있다.
.....
XXXXX
.....
XX...
.XXXX
그러나 위의 이런 두 번째 줄은 어느 쪽이 머리이고 어느 쪽이 꼬리인지 모르기 때문에 dp 두 가지로 결정한다
dp[i][j][k], dp에서 i행까지 왼쪽에는 j개가 위에 있고 오른쪽에는 k개가 있다
몇 개의 Trick:
....
X...
X...
....
X...
X...
이거 못 받아요......
X....
.....
X....
이것도 안 돼.#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
class Tunnels {
public:
int minimumTunnels(vector<string> );
};
bool visited[55][55];
int id[55][55];
int di, dj;
int n, m;
vector<string> s;
int dir[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };
void dfs(int i, int j) {
int k;
visited[i][j] = true;
for (k = 0; k < 4; ++k) {
int ii = i + dir[k][0];
int jj = j + dir[k][1];
if (ii < 0 || jj < 0 || ii >= n || jj >= m)
continue;
if (s[ii][jj] == 'X' && visited[ii][jj] == false) {
dfs(ii, jj);
break;
}
}
if (k == 4) {
di = i;
dj = j;
}
}
int dp[55][55][55];
int Tunnels::minimumTunnels(vector<string> ss) {
int i, j, k;
int ans = 0;
s = ss;
n = s.size();
m = s[0].size();
if (m == 1) {
for (i = 0; i < n; ++i)
if (s[i][0] == 'X')
return 1;
return 0;
}
memset(visited, 0, sizeof(visited));
memset(id, 0, sizeof(id));
for (j = 1; j < m - 1; ++j) {
if (s[0][j] != 'X')
continue;
int cnt = 0;
if (s[0][j - 1] == 'X')
cnt++;
if (s[0][j + 1] == 'X')
cnt++;
if (n != 1 && s[1][j] == 'X')
cnt++;
if (cnt <= 1 && visited[i][j] == false) {
ans++;
dfs(0, j);
id[di][dj] |= 2;
}
}
for (i = 0; i < n; ++i) {
j = 0;
if (s[i][j] == 'X' && visited[i][j] == false) {
int cnt = 0;
if (s[i][j + 1] == 'X')
cnt++;
if (i != n - 1 && s[i + 1][j] == 'X')
cnt++;
if (cnt != 2) {
dfs(i, j);
if (dj == m - 1 && di == i) {
id[i][j] = id[di][dj] = -1;
} else {
id[i][j] |= 1;
id[di][dj] |= 2;
}
}
}
j = m - 1;
if (s[i][j] == 'X' && visited[i][j] == false) {
dfs(i, j);
id[i][j] |= 1;
id[di][dj] |= 2;
}
}
memset(dp, -1, sizeof(dp));
dp[0][0][0] = 0;
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
for (k = 0; k < n; ++k) {
if (dp[i][j][k] == -1)
continue;
int jj, kk, add;
if (id[i][0] == id[i][m - 1] && id[i][m - 1] == -1) {
add = 0;
if (j > 0)
jj = j - 1;
else {
jj = j;
add++;
}
kk = k + 1;
if (dp[i + 1][jj][kk] == -1 || dp[i + 1][jj][kk]
> dp[i][j][k] + add)
dp[i + 1][jj][kk] = dp[i][j][k] + add;
add = 0;
if (k > 0)
kk = k - 1;
else {
kk = k;
add++;
}
jj = j + 1;
if (dp[i + 1][jj][kk] == -1 || dp[i + 1][jj][kk]
> dp[i][j][k] + add)
dp[i + 1][jj][kk] = dp[i][j][k] + add;
} else {
add = 0;
jj = j;
kk = k;
if (id[i][0] & 1) {
if (j > 0)
jj--;
else {
add++;
}
}
if (id[i][0] & 2) {
if (i == 0 || (id[i][0] == 2 && id[i - 1][0] != 1))
jj++;
if (i == 1 && (id[i][0] == 2 && id[i - 1][0] == 1))
jj++;
}
if (id[i][m - 1] & 1) {
if (k > 0)
kk--;
else {
add++;
}
}
if (id[i][m - 1] & 2) {
if (i == 0 || (id[i][m - 1] == 2 && id[i - 1][m - 1]
!= 1))
kk++;
if (i == 1 && (id[i][m - 1] == 2 && id[i - 1][m - 1]
== 1))
kk++;
}
if (dp[i + 1][jj][kk] == -1 || dp[i + 1][jj][kk]
> dp[i][j][k] + add)
dp[i + 1][jj][kk] = dp[i][j][k] + add;
}
}
}
}
int p = 1000000000;
for (j = 0; j <= n; ++j) {
for (k = 0; k <= n; ++k) {
if (dp[n][j][k] != -1)
p = min(p, dp[n][j][k]);
}
}
return ans + p;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
SRM 574먼저 연결 블록, 왼쪽 또는 오른쪽으로 나누어 다음과 같은 그림을 연결할 수 있다. 다섯 번째 줄을 이어서 세 번째 줄을 하나로 만들 수 있다. 이것은 욕심으로 해결할 수 있다. 그러나 위의 이런 두 번째 줄은 어느...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.