P12986 [GCJ 2022 #1A] Weightlifting 题解

思路分析：

数据范围是

100

，那么容易想到区间 DP。定义

F_{l,r}

表示完成动作

l\sim r

所需最小操作次数。转移如下：

F_{l,r}=\min_{k=l}^{r-1}F_{l,k}+F_{k+1,r}-2\times G_{l,r}

其中

G_{i,j}

表示动作

l\sim r

中重复的配重数（不必要的操作，直接压栈底即可），让

r

从

l+1

往右扫求出每个配重的最小值累加起来即可。为什么是

l+1

？就算是重复的

l

处也得加进去，还有最后要拿走，所以不能到

l

。初始化为

F_{i,i}=2\times G_{i,i}

，这里和上述转移的二倍皆为

1

次放入

1

次拿出。

AC Code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int x[N][N],f[N][N],g[N][N],mn[N];
void solve(){
	memset(g,0,sizeof(g));
	memset(f,0x3f,sizeof(f));
	int e,w;cin>>e>>w;
	for(int i=1;i<=e;i++){
		for(int j=1;j<=w;j++)
			cin>>x[i][j],g[i][i]+=x[i][j];
		f[i][i]=2*g[i][i];
	}
	for(int l=1;l<=e;l++){
		for(int j=1;j<=w;j++)mn[j]=x[l][j];
		for(int r=l+1;r<=e;r++){
			for(int j=1;j<=w;j++)mn[j]=min(mn[j],x[r][j]);
			for(int j=1;j<=w;j++)g[l][r]+=mn[j];
		}
	}
	for(int len=2;len<=e;len++)
		for(int l=1,r=len;r<=e;l++,r++)
			for(int k=l;k<r;k++)
				f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]-2*g[l][r]);
	cout<<f[1][e]<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    int T;cin>>T;for(int i=1;i<=T;i++)
    cout<<"Case #"<<i<<": ",solve();
    return 0;
}

完结撒花！！！

P12986 [GCJ 2022 #1A] Weightlifting 题解

文章操作

思路分析：

AC Code:

相关推荐

评论

P12986 [GCJ 2022 #1A] Weightlifting 题解