首页 > 代码库 > [uvalive 7263] Today Is a Rainy Day（暴力，BFS，dp）

[uvalive 7263] Today Is a Rainy Day（暴力，BFS，dp）

2024-09-20 11:33:20   215人阅读

题目链接：https://vjudge.net/problem/UVALive-7263

题意：给两个字符串a,b，只包含1~6的数字，现在允许两种操作：1、修改某一位数字，2、修改整个串的某个数字，变成另外一个数字。问从a到b的最少操作。

首先2操作修改的比较多，假如都能打到最优解的情况下，尽可能多的2操作一定会比较优。

我们可以先不考虑字符串具体的变化，先考虑只有6位数的2操作的变化情况。

以012345为起点，预处理出需要多少种2操作才可以变成一个6为的目标串。

不必关心每一种数字有多少个，只需要关心2操作最少多少次。上述操作直接bfs就行了。

接下来枚举012345变成000000到555555的所有最小状态作为中间状态，由于1操作的存在，所以仅仅进行2操作是会多进行多余的操作的。因此要记下输入字符串中每一种数字出现的次数，以及b到a每一对数字变化的次数。，用前者减去后者，加上枚举到的中间状态的最少步骤，求整个过程的最小值就是最优值。

 1 #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 const int maxn = 66666;
 6 const int inf = 0x7f7f7f7f;
 7 unordered_map<string, int> id;
 8 string di[maxn];
 9 int G[11][11], vis[11];
10 int icnt, n;
11 int dp[maxn];
12 string a, b;
13 queue<int> q;
14 string itmp;
15 
16 void dfs(int cnt) {
17     if(cnt == 6) {
18         id[itmp] = icnt; di[icnt++] = itmp;
19         return;
20     }
21     for(int i = 0; i < 6; i++) {
22         string bk = itmp;
23         itmp += (i + ‘0‘);
24         dfs(cnt+1);
25         itmp = bk;
26     }
27 }
28 
29 void init() {
30     string pre, cpy;
31     itmp.clear(); pre.clear(); id.clear(); icnt = 0;
32     dfs(0);
33     for(int i = 0; i < icnt; i++) dp[i] = inf;
34     for(int i = 0; i < 6; i++) pre += (i + ‘0‘);
35     while(!q.empty()) q.pop();
36     q.push(id[pre]); dp[id[pre]] = 0;
37     while(!q.empty()) {
38         int pid = q.front(); q.pop();
39         pre = di[pid];
40         for(int i = 0; i < 6; i++) {
41             for(int j = 0; j < 6; j++) {
42                 cpy = pre;
43                 for(int k = 0; k < 6; k++) {
44                     if(pre[k] == i + ‘0‘) cpy[k] = j + ‘0‘;
45                 }
46                 int cid = id[cpy];
47                 if(dp[cid] == inf) {
48                     dp[cid] = dp[pid] + 1;
49                     q.push(cid);
50                 }
51             }
52         }
53     }
54 }
55 
56 int main() {
57     // freopen("in", "r", stdin);
58     init();
59     cout << di[15115] << " " << dp[15115] << endl;
60     while(cin >> a >> b) {
61         memset(G, 0, sizeof(G));
62         memset(vis, 0, sizeof(vis));
63         n = a.length();
64         for(int i = 0; i < n; i++) {
65             int u = b[i] - ‘1‘;
66             int v = a[i] - ‘1‘;
67             G[u][v]++; vis[u]++;
68         }
69         int ret = inf;
70         for(int i = 0; i < icnt; i++) {
71             string mid = di[i];
72             int tmp = dp[i];
73             for(int j = 0; j < 6; j++) {
74                 tmp += vis[j] - G[j][mid[j]-‘0‘];
75             }
76             ret = min(ret, tmp);
77         }
78         printf("%d\n", ret);
79     } 
80     return 0;
81 }

 

[uvalive 7263] Today Is a Rainy Day（暴力，BFS，dp）


联系
我们