Round 1A 2022 - Code jam 2022 c.weightlifting (interval DP)

subject

time limit 20s,T(T<=100) Group example , common E(E<=100) Exercise times , Each exercise may require W(W<=100) Kind of barbell ,

The first i Tiandi j The number of barbell pieces required for each kind is Xij(0<=Xij<=100),

Put the barbell piece into a shape like 「 Stack 」 On the barbell rack ,

such as , The first day is AABA, The next day is AACCDD,

You need to put AABA, Bounce off A, Bounce off B,

And then put in C, Put in C, Put in D, Put in D, To get the barbell piece the next day

Finally, find the initial state of the barbell frame from empty , After exercise E Next time , Keep it empty ,

What is the minimum number of barbell pieces operated

Source of ideas

Official explanation

jiangly Code

Answer key

be aware , If the first [1,n] Some barbell pieces in this exercise are public ,

Then these barbell pieces can be directly padded under , First put , Finally take out , Then ignore these barbell pieces

Then consider divide and conquer , The first [l,r] The answer to this exercise can be [l,x] and [x+1,n] Get ,

Set the first [l,r] The barbell piece for this exercise is mn[l][r],

Is the first [l,r] Exercise times , It can be disassembled into ,

At first, put... In the stack mn[l][x] A barbell piece , Go ahead [l,x] Exercise times , After completion, play the stack and delete the barbell piece into mn[l][r] individual ,

Then pad barbell pieces so that the number of barbell pieces in the stack is mn[x+1][r] individual , Go ahead [x+1,r] Exercise times , Delete the barbell pieces after completion

The initial initialization length is 1 The range of , Its contribution is 2*mn[i][i], It means that the change of barbell piece is 0->mn[i][i]->0

Then when the intervals are merged , The change of barbell pieces before the merger is 0->mn[l][x]->0->mn[x+1][r]->0,

After the merger , The change of barbell piece is 0->mn[l][x]->mn[l][r]->mn[x+1][r]->0, That is, when consolidation occurs , Answer minus 2*mn[l][r]

Experience

Think of this public barbell piece trick 了 , But I still couldn't think of the interval in the end dp

I looked at the problems I had done , Discovery and hdu4283 You Are the One( Section DP) This question is very similar

The solution is based on jiangly It's written in code , The official solution is much the same .

Official explanation

dp[l][r] It's the second time [l,r] Exercise public barbell pieces （ The number is recorded as C[l,r]） Load the stack in advance , After exercising [l,r] Next time , Play the stack so that only this C[l,r] Minimum operation times of barbell pieces .

Consider enumerating an intermediate number of times x,dp[l][r]=min(dp[l][r],dp[l][x]+dp[x+1][r]+2*((C[l,x]-C[l,r])+(C[x+1,r]-C[l,r]))), Represents a process of disassembling into sub problems .

Exercise [l,r] These times , There are now public barbell pieces in the stack C[l,r] individual , Enter the stack first to turn the barbell pieces in the stack into C(l,x) individual , Go on with the second [l,x] Exercise times , Play the stack again to restore the barbell piece to C[l,r] individual , Re entering the stack turns the barbell piece into C[x+1,r] individual , Go on with the second [x+1,r] Exercise times , Play the stack again to restore the barbell piece to C[l,r] individual .

The final answer is dp[1][n]+2*C[1][n].

Or introduce empty elements 0、n+1, The final answer is dp[0][n+1].

Code

#include<bits/stdc++.h>
using namespace std;
const int N=105,INF=0x3f3f3f3f;
int t,n,m,dp[N][N],a[N][N],mn[N][N],now[N];
int main(){
    scanf("%d",&t);
    for(int ca=1;ca<=t;++ca){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                scanf("%d",&a[i][j]);
            }
        }
        memset(mn,0,sizeof mn);
        for(int l=1;l<=n;++l){
            memset(now,INF,sizeof now);
            for(int r=l;r<=n;++r){
                for(int j=1;j<=m;++j){
                    now[j]=min(now[j],a[r][j]);
                    mn[l][r]+=now[j];
                }
            }
        }
        for(int i=1;i<=n;++i){
            dp[i][i]=2*mn[i][i];
        }
        for(int len=2;len<=n;++len){
            for(int l=1;l+len-1<=n;++l){
                int r=l+len-1;
                dp[l][r]=INF;
                for(int k=l;k+1<=r;++k){
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]-2*mn[l][r]);
                }
            }
        }
        printf("Case #%d: %d\n",ca,dp[1][n]);
    }
    return 0;
}