P9541题解
Lysea
·
·
题解
Update 2023.8.16：
重新写了一份更格式化，观赏性更强的代码。
题意
如果你没有做过 P1216 数字三角形，请先去看看。
本题其实就是 P1216 的升级版，在原本的题目上做出了一下改编：
然后问你从顶部走到底部，路上经过的数字和最大是多少，此时所用的消耗值最小为多少。
（下文说的所有旋转都指顺时针旋转）
分析
不妨单独分析一下这两个新增的条件：
旋转原三角形后无非只存在三种可能，分别为旋转了 0 度，120 度，240 度后的结果，消耗值分别为 0，n，2 \times n。我们在后续的操作中可以对这三类进行分类讨论。
交换三角形中同一层的两个数，这两个数中必定存在且仅存在 1 个本层最大的数。
因为任意两个数交换的消耗值都是 1，跟其他数交换肯定无法比跟最大值交换好，所以其中至少有一个本层最大的数。
同时如果这两个数都是本层最大的数，那就没有交换的必要了，因此交换的两数中仅会存在 1 个本层最大的数。
因此我们可以对旋转后的三角形进行分类讨论，预处理出每层的最大值，然后就是常规的 dp 啦！
实现
设 dp_{i,j} 为走到第 i 行，第 j 列时经过数字和的最大值。
$m_i$ 为旋转后第 $i$ 行的最大值
-------------------------
对于旋转 $0$ 度的三角形，明显有：
$$dp_{i,j}=\max(dp_{i-1,j-1},dp_{i-1,j})+m_i$$
然后更新 $cost_{i,j}$ 为 $cost_{i-1,j-1}$ 或 $cost_{i-1,j}$。
最后如果 $dp_{i,j} \neq m_i$，$cost_{i,j} \rightarrow cost_{i,j}+1$。
--------------------------
对于旋转 $240$ 度的三角形，我们不需要真正去旋转它，只需要注意它与原三角形的相对位置关系，便可以直接在原三角形上 DP。
容易发现此时原三角形的列变为了行，$m_j$ 就相当于原三角形第 $j$ 列的最大值，有：
$$dp_{i,j}=\max(dp_{i,j+1},dp_{i+1,j+1})+m_j$$
注意上式中的 $i$ 和 $j$ 都要从大到小枚举，外层循环的是 $j$，以防止产生后效性。
然后更新 $cost_{i,j}$ 为 $cost_{i,j+1}$ 或 $cost_{i+1,j+1}$。
最后如果 $dp_{i,j} \neq m_j$，$cost_{i,j} \rightarrow cost_{i,j}+1$。
同时要注意，旋转三角形也会产生消耗值，所以这里记录的 $cost$ 数组不是消耗值的真实值，加上 $2 \times n$ 后才是。
--------------------------
对于旋转 $120$ 度的三角形，同样只需要注意它与原三角形的相对位置关系，便可以直接在原三角形上 DP。
此时的一层相当于原三角形一条斜线，很容易发现一条斜线上的 $i-j$ 是一个定值，且两两互不相同。
我们当然可以直接拿 $i-j$ 作为本层 $m$ 数组的下标，但因为上文中规定 $m_i$ 为旋转后第 $i$ 行的最大值，第 $k$ 层的 $i-j$ 实际上并不等于 $k$，所以这里也可以算出 $k$ 和 $i$，$j$ 之间的关系：
$$k=n-i+j$$
$m_{n-i+j}$ 就相当于旋转后第 $n-i+j$ 层的最大值，有：
$$dp_{i,j}=\max(dp_{i,j-1},dp_{i+1,j})+m_{n-i+j}$$
注意上式中的 $i$ 要从大到小枚举，$j$ 要从小到大枚举，外层循环的是 $i$，以防止产生后效性。
然后更新 $cost_{i,j}$ 为 $cost_{i,j-1}$ 或 $cost_{i+1,j}$。
最后如果 $dp_{i,j} \neq m_{n-i+j}$，$cost_{i,j} \rightarrow cost_{i,j}+1$。
同样的，这里记录的 $cost$ 数组也不是消耗值的真实值，加上 $n$ 后才是。
## 代码
```cpp
#include<bits/stdc++.h>
#define int unsigned long long
#define N 2005
using namespace std;
int n,y,z,a[N][N],dp[N][N],cost[N][N],maxn[N],ans,tot;
void Dy_Pr(int i,int j,int i1,int j1,int i2,int j2,int line,int extra){
// i 和 j 代表现在所处的坐标
// (i1,j1) 和 (i2,j2) 是可以转移到 (i,j) 的两个坐标
// line 表示一层
// extra 表示旋转产生的消耗值
if(dp[i1][j1]>dp[i2][j2]||(dp[i1][j1]==dp[i2][j2]&&cost[i1][j1]<cost[i2][j2])){
cost[i][j]+=cost[i1][j1];
dp[i][j]=dp[i1][j1];
}else{
cost[i][j]+=cost[i2][j2];
dp[i][j]=dp[i2][j2];
}
dp[i][j]+=maxn[line];
if(a[i][j]!=maxn[line]) cost[i][j]++;
if(ans<dp[i][j]||(ans==dp[i][j]&&cost[i][j]+extra<tot)){
ans=dp[i][j];
tot=cost[i][j]+extra;
}
}
void solve(int op){
for(int i=1;i<=n;i++){
maxn[i]=0;
for(int j=1;j<=n;j++){
dp[i][j]=0,cost[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(op==1) maxn[i]=max(maxn[i],a[i][j]);
if(op==2) maxn[j]=max(maxn[j],a[i][j]);
if(op==3) maxn[i-j]=max(maxn[i-j],a[i][j]);
}
}
if(op==1){
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
Dy_Pr(i,j,i-1,j-1,i-1,j,i,0);
}
}
}
if(op==2){
for(int j=n;j;j--){
for(int i=n;i>=j;i--){
Dy_Pr(i,j,i,j+1,i+1,j+1,j,2*n);
}
}
}
if(op==3){
for(int i=n;i;i--){
for(int j=1;j<=i;j++){
Dy_Pr(i,j,i,j-1,i+1,j,i-j,n);
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
solve(1);//旋转 0 度
solve(2);//旋转 240 度
solve(3);//旋转 120 度
cout<<ans<<" "<<tot;
return 0;
}
```
老代码：
```cpp
#include<bits/stdc++.h>
#define int unsigned long long
#define N 2005
using namespace std;
int n,y,z,a[N][N],dp[N][N],cost[N][N],maxn[N],ans,tot;
signed main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
//不旋转的情况:
for(int i=1;i<=n;i++){
maxn[i]=0;
for(int j=1;j<=n;j++){
dp[i][j]=0,cost[i][j]=0;
}
}//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
maxn[i]=max(maxn[i],a[i][j]);
}
}//预处理
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(dp[i-1][j-1]>dp[i-1][j]||(dp[i-1][j-1]==dp[i-1][j]&&cost[i-1][j-1]<cost[i-1][j])){
cost[i][j]+=cost[i-1][j-1];
dp[i][j]=dp[i-1][j-1];
}else{
cost[i][j]+=cost[i-1][j];
dp[i][j]=dp[i-1][j];
}
dp[i][j]+=maxn[i];
if(a[i][j]!=maxn[i]) cost[i][j]++;
if(ans<dp[i][j]||(ans==dp[i][j]&&cost[i][j]<tot)){//更新答案
ans=dp[i][j];
tot=cost[i][j];
}
}
}
//旋转 240 度的情况:
for(int i=1;i<=n;i++){
maxn[i]=0;
for(int j=1;j<=n;j++){
dp[i][j]=0,cost[i][j]=0;
}
}//初始化
for(int j=1;j<=n;j++){
for(int i=j;i<=n;i++){
maxn[j]=max(maxn[j],a[i][j]);
}
}//预处理
for(int j=n;j;j--){
for(int i=n;i>=j;i--){//注意这里的循环顺序
if(dp[i][j+1]>dp[i+1][j+1]||(dp[i][j+1]==dp[i+1][j+1]&&cost[i][j+1]<cost[i+1][j+1])){
cost[i][j]+=cost[i][j+1];
dp[i][j]=dp[i][j+1];
}else{
cost[i][j]+=cost[i+1][j+1];
dp[i][j]=dp[i+1][j+1];
}
dp[i][j]+=maxn[j];
if(a[i][j]!=maxn[j]) cost[i][j]++;
if(ans<dp[i][j]||(ans==dp[i][j]&&cost[i][j]+n*2<tot)){//更新答案
ans=dp[i][j];
tot=cost[i][j]+n*2;//别忘了加上旋转产生的消耗值
}
}
}
//旋转 120 度的情况:
for(int i=1;i<=n;i++){
maxn[i]=0;
for(int j=1;j<=n;j++){
dp[i][j]=0,cost[i][j]=0;
}
}//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
maxn[i-j]=max(maxn[i-j],a[i][j]);
}
}//预处理(这里为了方便就直接拿 i-j 作为数组下标了)
for(int i=n;i;i--){
for(int j=1;j<=i;j++){//注意这里的循环顺序
if(dp[i][j-1]>dp[i+1][j]||(dp[i][j-1]==dp[i+1][j]&&cost[i][j-1]<cost[i+1][j])){
cost[i][j]+=cost[i][j-1];
dp[i][j]=dp[i][j-1];
}else{
cost[i][j]+=cost[i+1][j];
dp[i][j]=dp[i+1][j];
}
dp[i][j]+=maxn[i-j];
if(a[i][j]!=maxn[i-j]) cost[i][j]++;
if(ans<dp[i][j]||(ans==dp[i][j]&&cost[i][j]+n<tot)){//更新答案
ans=dp[i][j];
tot=cost[i][j]+n;//别忘了加上旋转产生的消耗值
}
}
}
cout<<ans<<" "<<tot;
return 0;
}
```