题解：P8488 「Wdoi-(-1)」恋弹者们的黑集市
Yore_Snow
·
·
题解
思路：
一个骰子有六个面。
如果确定三个面，另外三个面对应的也就知道了。
我们把一个骰子的三个面（前、右、上）分别记作 1,2,3。另外三个面，1 对应的面为 6，2 对应的面为 4，3 对应的面为 5。
按照这三个面，滚动时有 3\times 8=24 个不同的面。
初始时，前、右、上三个面是 1,2,3。不同角度的面有 8 个（在代码中）。
很显然，如果当前的骰子状态，也就是前、右、上的等于 $a,b,c$，那么 $dp_{i,j,k}=\max\{dp_{i,j-1,(a,\overline{c},b)},dp_{i-1,j,(\overline{c},b,a)}\}$。
### 代码：
1. 输入：
```cpp
cin >> n >> m;
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
cin >> a[i][j];
}
}
cin >> w[1] >> w[6] >> w[4] >> w[2] >> w[3] >> w[5];
```
注意 `w` 不是按顺序输入的。
2. 处理 $8$ 个不同角度的前、右、上：
```cpp
v.push_back({1,4,5});
v.push_back({4,6,5});
v.push_back({6,2,5});
v.push_back({2,1,5});
v.push_back({1,2,3});
v.push_back({2,6,3});
v.push_back({6,4,3});
v.push_back({4,1,3});
```
3. 将原本的骰子进行滚动：
```cpp
for (int i = 0;i < 8;i++){ // 原本有 8 个
v.push_back({v[i].z,v[i].x,v[i].y});
v.push_back({v[i].y,v[i].z,v[i].x});
}
```
4. 将所有合法的状态标记在 `k` 数组中：
```cpp
for (int i = 0;i < 24;i++){
kk[v[i].x][v[i].y][v[i].z] = i; // 在 v 中的位置
}
```
5. 初始化：
```cpp
memset(dp,-0x3f,sizeof(dp));
dp[1][1][kk[1][2][3]] = a[1][1] * w[5]; // 第一个位置
```
6. 转移：
```cpp
for (int i = 1;i <= n;i++){
for (int j = 1;j <= m;j++){
if (i == 1 && j == 1) continue;
for (int k = 0;k < 24;k++){
int aa = v[k].x; // 前
int b = v[k].y; // 右
int c = v[k].z; // 上
dp[i][j][k] = max(dp[i][j-1][kk[aa][dui(c)][b]],dp[i-1][j][kk[dui(c)][b][aa]])+a[i][j] * w[dui(c)];
}
}
}
```
7. 统计答案：
在所有状态里取一个最大的。
```cpp
int ans = INT_MIN;
for (int k = 0;k < 24;k++){
ans = max(ans,dp[n][m][k]);
}
cout<<ans;
```