自动搬运

查看原文

来自洛谷，原作者为

	Aesyl 夏洛特&友利奈绪最可爱LA！

搬运于2025-08-24 22:49:22，当前版本为作者最后更新于2023-08-15 18:54:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Update 2023.8.16：

重新写了一份更格式化，观赏性更强的代码。

题意

如果你没有做过 P1216 数字三角形，请先去看看。

本题其实就是 P1216 的升级版，在原本的题目上做出了一下改编：

• 给出的三角形可以顺时针进行 $120$ 度旋转，旋转一次消耗值为 $n$。

• 给出的三角形在旋转过后，可以交换同一层中的任意两个数，交换一次消耗值为 $1$。

然后问你从顶部走到底部，路上经过的数字和最大是多少，此时所用的消耗值最小为多少。

（下文说的所有旋转都指顺时针旋转）

分析

不妨单独分析一下这两个新增的条件：

旋转原三角形后无非只存在三种可能，分别为旋转了 $0$ 度，$120$ 度，$240$ 度后的结果，消耗值分别为 $0$，$n$，$2 \times n$。我们在后续的操作中可以对这三类进行分类讨论。

交换三角形中同一层的两个数，这两个数中必定存在且仅存在 $1$ 个本层最大的数。

因为任意两个数交换的消耗值都是 $1$，跟其他数交换肯定无法比跟最大值交换好，所以其中至少有一个本层最大的数。

同时如果这两个数都是本层最大的数，那就没有交换的必要了，因此交换的两数中仅会存在 $1$ 个本层最大的数。

因此我们可以对旋转后的三角形进行分类讨论，预处理出每层的最大值，然后就是常规的 dp 啦！

实现

设 $dp_{i,j}$ 为走到第 $i$ 行，第 $j$ 列时经过数字和的最大值。

$cost_{i,j}$ 为走到第 $i$ 行，第 $j$ 列时满足 $dp_{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$ 后才是。

代码

#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;
}

老代码：

#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;
}