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:

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

完结撒花！！！