Flower shop window layout [dynamic planning]

Flower shop window decoration 【 Dynamic programming 】

Title Description

AC Code

#include<bits/stdc++.h>
using namespace std;

int f,v;
int a[105][105], dp[105][105], cho[105][105];

void find(int x, int y){
            // Find a path 
    if (!x)             // The first 0 End of bouquet 
        return;
    if (cho[x][y])      // If the first x Bunch of flowers on the y A vase 
        find(x - 1,y - 1),cout<<y<<" "; // First, find out the second x-1 Bunch of flowers on the y-1 A vase 
    else
        find(x, y - 1); // Find the first x Bunch of flowers on the y-1 A vase 
}

signed main(){
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>f>>v;
    for(int i = 1;i <= f;++i){
    
        for (int j = 1; j <= v; ++j) {
    
            cin>>a[i][j];
        }
    }
    memset(dp,-0x3f,sizeof dp);     // Initialize to negative infinity 
    for (int i = 0; i <= v; ++i) {
    
        dp[0][i] = 0;                   // initialization 
    }
    for (int i = 1; i <= f; ++i) {
          // Traverse each bunch of flowers 
        for (int j = 1; j <= v; ++j) {
      // Traverse each vase 
            if (dp[i - 1][j - 1] + a[i][j] > dp[i][j]) // The first i Bunch of flowers on the j A vase 
                dp[i][j] = dp[i - 1][j - 1] + a[i][j], cho[i][j] = true;
            if (dp[i][j - 1] > dp[i][j])    // If you put it in j-1 The previous effect is better 
                dp[i][j] = dp[i][j - 1], cho[i][j] = false;
        }
    }
    cout<<dp[f][v]<<"\n";
    find(f, v);
    return 0;
}

/* 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 53 2 4 5 */