[Codeforces517D] Minimum path (DP, 贪心, 搜索)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：http://codeforces.com/contest/1072/problem/D

给一个$n\times n$的字母阵，允许修改其中的$k$个字符，问从$(1,1)$走到$(n,n)$字典序最小的字符串。

如果不考虑替换的话，字典序最小的字符串可以由BFS得到。

如果考虑替换的话，首先知道替换掉的字符肯定都会把不是’a’的换成’a’。

接下来考虑DP，维护$dp(i,j)$为走到$(i,j)$处最多的’a’数量，这里不考虑$k$次替换。

由于是字典序最小，那么我们知道越早替换成’a’字典序一定是最小的，因此我们就确定了贪心地替换前面扫描的非’a’字符这样一个转移的无后效性。

DP转移可以这样：
$$
dp(i,j)=max(dp(i-1,j),dp(i,j-1))+(G(i,j)==’a’)
$$
接着考虑是否有足够的替换次数，于是存在$i+j-1-dp(i,j)$个待替换的非’a’字符，显然都替换掉字典序是最小的，于是我们拿这个和$k$比一下就可以确定当前字符$G(i,j)$是否需要替换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;
const int maxn = 2020;
int n, k;
char G[maxn][maxn];
queue<pii> pq;
int p[maxn][maxn];
vector<char> ret;
bool flag;
int dp[maxn][maxn];

bool ok(int x, int y) {
  return x >= 1 && x <= n && y >= 1 && y <= n;
}

void dfs(int x, int y) {
  if(x == 1 && y == 1) {
    reverse(ret.begin(), ret.end());
    int cnt = 0;
    for(int i = 0; i < ret.size(); i++) {
      printf("%c", ret[i]);
    }
    printf("\n");
    flag = 1;
    return;
  }
  if(ok(x-1,y)&&p[x-1][y]) {
    ret.push_back(G[x-1][y]);
    dfs(x-1,y);
    if(flag) return;
    ret.pop_back();
  }
  if(ok(x,y-1)&&p[x][y-1]) {
    ret.push_back(G[x][y-1]);
    dfs(x,y-1);
    if(flag) return;
    ret.pop_back();
  }
}

bool vis[maxn][maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&k)) {
    flag = 0;
    memset(vis, 0, sizeof vis);
    memset(p, 0, sizeof p);
    memset(dp ,0, sizeof(dp));
    for(int i = 1; i <= n; i++) {
      scanf("%s", G[i]+1);
    }
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (G[i][j] == 'a');
        if(i + j - 1 - dp[i][j] <= k) G[i][j] = 'a';
      }
    }
    pq.push(pii(1, 1));
    p[1][1] = 1;
    while(!pq.empty()) {
      vector<pii> tmp;
      int cur = 200;
      while(!pq.empty()) {
        tmp.push_back(pq.front());
        cur = min(cur, (int)G[pq.front().first][pq.front().second]);
        pq.pop();
      }
      for(int i = 0; i < tmp.size(); i++) {
        int x = tmp[i].first, y = tmp[i].second;
        if(cur == (int)G[x][y]) {
          p[x][y] = 1;
          if(ok(x+1, y)&&!vis[x+1][y]) {
            vis[x+1][y] = 1;
            pq.push(pii(x+1, y));
          }
          if(ok(x, y+1)&&!vis[x][y+1]) {
            vis[x][y+1] = 1;
            pq.push(pii(x, y+1));
          }
        }
      }
    }
    ret.clear();
    ret.push_back(G[n][n]);
    dfs(n,n);
  }
  return 0;
}