Flower shop window (linear DP)

Flower shop windows

link ：https://ac.nowcoder.com/acm/contest/24213/1005

Title Description
Small q And his wife z Recently opened a flower shop , They are going to put all the best flowers in the shop in the window .

But they have many vases , Each vase has its own characteristics , therefore , When you put different bouquets in each vase , It has different aesthetic effects .

In order to make the flowers in the window most suitable , They have to find a way to arrange the placement of each flower .

But because of the small q And small z Too busy every day , There is no time to design the arrangement of flowers in the window , So they want you to help them find out the most beautiful flowers and the position of each flower .

Each flower has a logo , Suppose that the number of identification of Rhododendron is 1, The mark number of Begonia is 2, The identification number of carnation is 3, All bouquets must be placed in the vase in the order of their identification number , namely ：

Azaleas must be placed in the vase on the left of Begonia , Begonia must be placed in the vase on the left of the carnation .

If the number of vases is greater than the number of bouquets . The extra vases must be left empty , And only one bunch of flowers can be placed in each vase .

Each flower in a different bottle will produce a different degree of beauty , The aesthetic degree may be positive or negative .

In the above example , The beauty degree of different collocations of vases and bouquets , As shown in the following table ：

 flowers      bottle 
                  1     2    3    4    5
   1 ( azalea )     7    23   -5  -24   16
   2 ( Begonia )     5    21   -4   10   23
   3 ( Carnation )    -21    5   -4  -20   20

According to the table , The azaleas are in the vase 2 in , It's going to look great ; But if it's in a vase 4 The middle is very ugly .

For maximum Aesthetics , You must keep the order of the bouquet , To maximize the aesthetic value of the bouquet , And find out the number of the vase that each kind of flower should be placed .

Input description :
The first 1 That's ok ： Two integers F and V, Expressing common ownership F grow flowers ,V A vase .
The first 2 Go to the first place F+1 That's ok ： Each row has V Number , It indicates the beauty degree of flowers placed in different vases value.( Aesthetic degree and less than 2^31, There are positive and negative aesthetic degrees )
Output description :
There are two lines of output ： The first line outputs the value of the sum of the maximum aesthetics , The second line has F The number indicates the number of vases each flower should be placed in .
If there are multiple solutions , The output dictionary order is smaller （ Under the condition that the aesthetic degree remains unchanged , Put the flowers forward as far as possible ）.
Example 1
Input

3 5 
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

Output

53
2 4 5

remarks :
1≤F≤V≤100

Answer key
Topic test site ： Two dimensional linear DP （ Beginners can refer to the code to simulate the process of state transition , It is helpful to understand the state transition in the future ）

The main idea of the topic ：n grow flowers m A vase , The vase sequence and the sequence in which the flowers are inserted are fixed , Each kind of flower looks different in each vase （ There are negative numbers ）, Ask and tell n Where to plant flowers n The most beautiful of the vases .

Topic analysis ： For the first i grow flowers , The maximum aesthetics it can obtain is ： Within the legal range , The most beautiful position in the vase behind the location of the previous flower （ The legal range refers to the last flower ( The last kind of flower k maintain ) Start at the right place , To make i In the back, there is an area where the vase can be placed , For example, according to the sample topic , For the first 2 For planting flowers , The last place it can be placed is 4, At least... Is left in the back 1 The position of a vase ）.
So the transfer equation ：dp [ i ][ j ] = max (dp [ i ][ j ], dp [ i-1 ][ k ] + v [ i ][ j ]);

Principle analysis of transfer equation :
dp[i][j] Before presentation i Before planting flowers j The greatest beauty a vase can get
The first i The greatest beauty you can get from planting flowers is only the same as that of i - 1 Planting flowers is related to the beauty of the legal space , So use the first one i - 1 To update the beauty of the flowers i Plant flowers in the j The maximum beauty of vases

AC Code

#include <iostream>
using namespace std;
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);
int dp[110][110],w[110][110];
int pos[110];
const int INF = 0x3f3f3f3f;
int f,v;
int ans = -INF;

int main(){
    IOS;
    cin >> f >> v;
    for(int i = 1;i <= f;i ++)
        for(int j = 1;j <= v;j ++){
            cin >> w[i][j];
            dp[i][j] = -INF; // Because there are negative numbers , Guarantee the maximum 
        }
    
    for(int i = 1;i <= f;i ++){
        for(int j = i;j <= v - (f - i);j ++){
        // details  :  The first i Flowers were planted in the first place i A vase  +  Legal interval 
            for(int k = i - 1;k < j;k ++){
            // details  : k Used for maintenance i-1 The legal range for planting flowers , So subtract 1, And then according to section i-1 The value in the seed flower updates the i grow flowers 
                dp[i][j] = max(dp[i][j],dp[i - 1][k] + w[i][j]);
            }
        }
    }

    for(int i = 1; i <= v; i++)
        ans = max(ans, dp[f][i]);
    cout << ans << endl;
    
    int idx = f;
    for(int i = f;i >= 1;i --){
        for(int j = 1;j <= v;j ++){
            if(dp[i][j] == ans){
                pos[--idx] = j;
                ans -= w[i][j];
                break;
            }
        }
    }
    for(int i = 0;i < f;i ++){
        cout << pos[i] << " ";
    }
    
    return 0;
}