Problem
Solution
通过题目意思发现,有三种情况:
-
没有旋转的初始情况
-
旋转一次的情况
-
旋转两次的情况
我们考虑怎么处理初始情况,其他情况同理。
首先,我们发现经过数和最大一定可以保证是每行的最大值的总和,所以只要计算最小的消耗就可以了。
考虑 DP,设 \(dp_{i,j}\) 表示从上往下走到 \(i,j\) 时使每行都取最大值时的最小消耗。
容易想到如果当前的数就是当前行的最大值,便可以直接从 \(dp_{i-1,j-1}\) 和 \(dp_{i-1,j}\) 转移过来;如果不是,则只需再加 \(1\) 即可(因为可以调换任意两个数的位置)。
每行的最大值预处理或者动规时处理均可。
注意边界和初始值。
Code
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i>=(b);i--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define elif else if
// #define int long long
const int N=1e3+4,INF=INT_MAX;
int n,a[N][N],b[N][N],Maxsum,Minmagic,Max[N],dp[N][N];
void work(int sum,int magic)
{
For(i,1,n)Max[i]=0;
For(i,1,n)For(j,1,i)dp[i][j]=INF,Max[i]=max(Max[i],a[i][j]);
For(i,1,n)sum+=Max[i];
For(i,1,n)
For(j,1,i)
if(a[i][j]==Max[i])dp[i][j]=min(dp[i][j],min(dp[i-1][max(1,j-1)],dp[i-1][min(i-1,j)]));
else dp[i][j]=min(dp[i][j],min(dp[i-1][max(1,j-1)],dp[i-1][min(i-1,j)])+1);
int Min=INF;
For(i,1,n)Min=min(Min,dp[n][i]);
magic+=Min;
if(sum>Maxsum)Maxsum=sum,Minmagic=magic;
elif(sum==Maxsum)Minmagic=min(Minmagic,magic);
}
signed main()
{
IOS;
cin>>n;
For(i,1,n)For(j,1,i)cin>>a[i][j];
work(0,0);
For(i,1,n)For(j,1,i)b[i][j]=a[i][j];
For(i,1,n)For(j,1,i)a[i][j]=b[n+1-j][i-j+1];
// For(i,1,n){For(j,1,i)cout<<a[i][j]<<" ";cout<<"\n";}
work(0,n);
For(i,1,n)For(j,1,i)b[i][j]=a[i][j];
For(i,1,n)For(j,1,i)a[i][j]=b[n+1-j][i-j+1];
// For(i,1,n){For(j,1,i)cout<<a[i][j]<<" ";cout<<"\n";}
work(0,2*n);
cout<<Maxsum<<" "<<Minmagic;
return 0;
}
标签:洛谷,min,int,题解,sum,P9541,Max,magic,dp
From: https://www.cnblogs.com/Wu-ZH/p/18357791