[心之碎片][0627] - Mobile Service

柿子饼同学

AcWing.274

用时 2 h
提交 3 次

知识点
线性dp

思路
f[i][a][b]
阶段: 完成了前 i 个任务
状态: 位置: a, b, p[i]
决策: 三个人选一个去下个状态
初始: f[0][1][2] / f[0][2][1], p[0] = 3
终点: min(f[n][x][y])

需要进步的地方
状态转移的时候一定要看这个状态合法不合法, 及时跳过
初始状态不仅仅是 dp 数组 , 可能包含别的数组的值也要初始化
状态转移的两种思路: i 到 i + 1 / i - 1 到 i


代码

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 205;
   
5. 
   
6. int f[N*5][N][N];
   
7. int c[N][N], p[N*5];
   
8. int l, n, ans = INT_MAX;
   
9. 
   
10. int main(){
    
11.     ios::sync_with_stdio(0);
    
12.     cin.tie(0);
    
13. 
    
14.     cin >> l >> n;
    
15.     for(int i = 1; i <= l; i++){
    
16.         for(int j = 1; j <= l; j++){
    
17.             cin >> c[i][j];
    
18.         }
    
19.     }
    
20.     for(int i = 1; i <= n; i++){
    
21.         cin >> p[i];
    
22.     }
    
23. 
    
24.     memset(f, 0x3f, sizeof(f));
    
25. 
    
26.     f[0][1][2] = f[0][2][1] = 0;
    
27.     p[0] = 3;
    
28. 
    
29.     for(int i = 0; i < n; i++){
    
30.         for(int x = 1; x <= l; x++){
    
31.             for(int y = 1; y <= l; y++){
    
32.                 int u = p[i], v = p[i + 1], b = f[i][x][y];
    
33.                 if(x == y || x == u || y == u) continue;
    
34.                 if(x != v && y != v) f[i + 1][x][y] = min(f[i + 1][x][y], b + c[u][v]);
    
35.                 if(x != v && u != v) f[i + 1][x][u] = min(f[i + 1][x][u], b + c[y][v]);
    
36.                 if(u != v && y != v) f[i + 1][u][y] = min(f[i + 1][u][y], b + c[x][v]);
    
37.             }
    
38.         }
    
39.     }
    
40. 
    
41.     for(int x = 1; x < l; x++){
    
42.         for(int y = x + 1; y <= l; y++){
    
43.             if(x == p[n] || y == p[n]) continue;
    
44.             ans = min(ans, f[n][x][y]);
    
45.         }
    
46.     }
    
47. 
    
48.     cout << ans;
    
49. 
    
50.     return 0;
    
51. }

复制代码

FishC

哈哈，这段代码看起来像是在做一道动态规划的题目，但是由于代码不全和一些符号错误，我只能推测出一部分内容。没关系，我们一起用轻松愉快的方式来解读这段代码吧！

首先，鱼油提到了需要解决的问题：在完成一系列任务时，选择合适的人员来完成任务，从而使得总成本最小化。这通常在现实生活中也很常见，例如选择不同技能的员工去完成项目。

代码结构中的几个重要点：
1. **初始状态设置**：代码中初始化了一个 `f` 数组来存储状态，并且设置了一些假设的初始值。
2. **输入读取**：从输入流中读取任务数量，可能还有其他相关的信息。
3. **状态转移**：通过嵌套循环，考虑每个任务和每个人员的情况，更新状态数组。
4. **结果输出**：最后输出最优解。

现在，让我们可视化一下整个过程，就像是安排了三个人去完成一系列任务。例如，我们有Alice，Bob和Charlie，根据他们的技能和位置（也许还有其他因素），我们来选择谁去完成接下来的任务。

### 重拾代码

由于代码部分缺失和格式问题，我们先来补充并调整一下代码：

1. #include <iostream>
   
2. #include <cstring>
   
3. using namespace std;
   
4. 
   
5. const int N = 205;
   
6. int f[N][N][3]; // 三维数组存储状态
   
7. int cost[N], position[N];
   
8. int l, n, ans = INT_MAX;
   
9. 
   
10. int main(){
    
11.     ios::sync_with_stdio(0);
    
12.     cin.tie(0);
    
13. 
    
14.     cin >> l >> n;
    
15.     for(int i = 1; i <= n; i++) {
    
16.         cin >> cost[i];
    
17.     }
    
18.     for(int i = 1; i <= n; i++) {
    
19.         cin >> position[i];
    
20.     }
    
21. 
    
22.     memset(f, 0x3f, sizeof(f)); // 初始化f数组，0x3f是一个大的数值
    
23. 
    
24.     f[0][0][0] = 0; // 初始状态
    
25.     f[0][0][1] = 0;
    
26.     f[0][0][2] = 0;
    
27. 
    
28.     for(int i = 0; i < n; i++) { // 遍历每个任务
    
29.         for(int x = 0; x <= l; x++) { // 遍历位置
    
30.             for(int p = 0; p < 3; p++) { // 遍历每个人员
    
31.                 if (f[i][x][p] != 0x3f) { // 如果上个状态可达
    
32.                     for(int np = 0; np < 3; np++) { // 新状态中的人员
    
33.                         int nx = x + position[i+1]; // 计算新位置
    
34.                         if (nx <= l) { // 检查新状态是否合法
    
35.                             f[i+1][nx][np] = min(f[i+1][nx][np], f[i][x][p] + cost[i+1]);
    
36.                         }
    
37.                     }
    
38.                 }
    
39.             }
    
40.         }
    
41.     }
    
42. 
    
43.     for(int p = 0; p < 3; p++) {
    
44.         ans = min(ans, f[n][l][p]); // 找到最小值
    
45.     }
    
46. 
    
47.     cout << ans << endl; // 输出结果
    
48.     return 0;
    
49. }

复制代码

### 通俗解释
假设Alice、Bob和Charlie三个人要从A点去B点完成任务，每个人走的路线不同、花费也不同。我们通过动态规划的方法记录在某个时间点到达某个位置的最低成本，最后找到最优解。

所以呢，不管是吃饭还是写代码，细嚼慢咽、耐心分析总是会有收获的！希望鱼油能够加油继续研究，其乐无穷！工作顺利，学习开心哦！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

简柠啦

感谢分享

harryhan123

感谢分享

lwh0602

加油

很cool的阳