Educational Codeforces Round 97 (Rated for Div. 2) C. Chef Monocarp (DP)

题意:有\(n\)个菜在烤箱中,每个时刻只能将一个菜从烤箱中拿出来,第\(i\)个时刻拿出来的贡献是\(|i-a[i]|\),你可以在任意时刻把菜拿出来,问将所有菜拿出的最小贡献是多少?
题解: 先对所有菜从小到大排序,因为\(a_i\)单调,我们可以枚举时刻\([1,2*n]\)来进行DP,先更新第一道菜的状态,然后再更新后面的状态,每道菜可以由当前时刻之前的前一道菜的状态转移而来,所以写出状态转移方程:\(dp[i][j]=min(dp[i-1][k]+abs(j-a[i]),dp[i][j])\).

题解:

int t;

int n;

int a[N];

int dp[4000][4000];

int ans;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

        cin>>n;

        ans=INF;

        for(int i=1;i<=n;++i) cin>>a[i];

        sort(a+1,a+1+n);

        me(dp,INF,sizeof(dp));

        for(int i=1;i<=4*n;++i) dp[1][i]=abs(i-a[1]);

        for(int i=2;i<=n;++i){

            for(int j=i;j<=4*n;++j){

                for(int k=1;k<j;++k){

                    dp[i][j]=min(dp[i-1][k]+abs(j-a[i]),dp[i][j]);

                }

            }

        }

        for(int i=1;i<=4*n;++i) ans=min(ans,dp[n][i]);

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

Educational Codeforces Round 97 (Rated for Div. 2) C. Chef Monocarp (DP)

最新文章

热门文章