Codeforces Round #108(Div.2)-상태 압축 DP+spfa+dfs-Garden
6168 단어 codeforces
For each garden square we know number aij that represents the number of flowers that grow in the square with coordinates (i, j). When a square is covered with concrete, all flowers that grow in the square die.
Vasya wants to cover some squares with concrete so that the following conditions were fulfilled:
As Vasya has a rather large garden, he asks you to help him.
Input
The first input line contains three integers n, m and k (1 ≤ n, m ≤ 100, n·m ≤ 200, 1 ≤ k ≤ min(n·m, 7)) — the garden's sizes and the number of the important squares. Each of the next n lines contains m numbers aij (1 ≤ aij ≤ 1000) — the numbers of flowers in the squares. Next k lines contain coordinates of important squares written as "x y"(without quotes) (1 ≤ x ≤ n, 1 ≤ y ≤ m). The numbers written on one line are separated by spaces. It is guaranteed that all k important squares have different coordinates.
Output
In the first line print the single integer — the minimum number of plants that die during the road construction. Then print n lines each containing m characters — the garden's plan. In this plan use character "X"(uppercase Latin letter X) to represent a concrete-covered square and use character "."(dot) for a square that isn't covered with concrete. If there are multiple solutions, print any of them.
Sample test(s)
input
3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3
output
9
.X.
.X.
.XX
input
4 5 4
1 4 5 1 2
2 2 2 2 7
2 4 1 4 5
3 2 1 7 1
1 1
1 5
4 1
4 4
output
26
X..XX
XXXX.
X.X..
X.XX.
:http://blog.csdn.net/gzh1992n/article/details/9119543
/*
: k ,
dp[i][j] i , j
1: dp[i][j] = min(dp[k][j] + maze[k][i]) ,
2: dp[i][j] = min(dp[i][j1] + dp[i][j2] - maze[i/m][i%m]) j1,j2 j
dfs
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <map>
using namespace std;
const int inf = 1 << 29;
const int MAX = 200 + 10;
int dp[MAX][1<<7], pre[MAX][1<<7];
int n, m, k, nn, mm;
int hash1[MAX];
int maz[MAX][MAX];
char g[MAX][MAX];
bool visit[MAX][1<<7];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
struct Node {
int u, st;
Node(int _u, int _st){
u = _u, st = _st;//
}
};
queue<Node> que;
bool check(int x, int y) {
if(x >= 0 && x < n && y >= 0 && y < m) return true;
return false;
}
//update(u, hash[u], maz[a][b], -1);
void update(int u, int st, int w, int fa) {
if(dp[u][st] > w) {
dp[u][st] = w;
pre[u][st] = fa;//
if(!visit[u][st]) {
que.push(Node(u, st));
visit[u][st] = true;
}
}
}
void dfs(int u, int st) {
int x = u / m, y = u % m;
g[x][y] = 'X';
if(pre[u][st] == -1) return;//
else {
int v = pre[u][st] / 1000, stt = pre[u][st] % 1000;
dfs(v, stt);
if(stt - st) dfs(v, st - stt);//
}
}
void solve() {//spfa
while(!que.empty()) {
Node now = que.front();
que.pop();
int u = now.u, x = now.u / m, y = now.u % m, st = now.st;
visit[u][st] = false;//
for(int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if(!check(xx, yy)) continue;
int v = xx * m + yy;
update(v, st, dp[u][st] + maz[xx][yy], u * 1000 + st);//
}
int t = mm - 1 - st;
for(int i = t; i; i = (i-1) & t) {
update(u, i | st, dp[u][i] + dp[u][st] - maz[x][y], u * 1000 + st);// ,
}
}
int ans = inf, u;
for(int i = 0; i < nn; i++) {
if(ans > dp[i][mm-1]) {
ans = dp[i][mm-1];
u = i;
}
}//
dfs(u, mm - 1);//DFS
cout << ans << endl;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++)
cout << g[i][j];
cout << endl;
}
}
int main() {
while(cin >> n >> m >> k) {
while(!que.empty()) que.pop();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> maz[i][j];
g[i][j] = '.';//
}
}
nn = n * m, mm = 1 << k;//
memset(hash1, 0, sizeof(hash1));
memset(visit, false, sizeof(visit));
for(int i = 0; i < nn; i++)
for(int j = 0; j < mm; j++)
dp[i][j] = inf;// ,
for(int i = 0, a, b; i < k; i++) {
cin >> a >> b;
a--, b--;
int u = a * m + b;
hash1[u] = 1 << i;//
update(u, hash1[u], maz[a][b], -1);
}
solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.