Informatics Olympiad all in one 1279: [example 9.23] window layout | window layout of Luogu p1854 flower shop

【 Topic link 】

ybt 1279：【 example 9.23】 Window display (flower)
Luogu P1854 Flower shop window decoration
Make complaints ： In the test data given in the "one pass" , The minus sign is Full angle minus sign ！ No wonder the program ends every time the data cannot be read . Let's use the test data of Luogu .

【 Topic test site 】

1. Dynamic programming

【 Their thinking 】

1. State definition

aggregate ： The scheme of arranging flowers
Limit ： Choose the first few flowers , In the first few bottles
attribute ： Aesthetic value
Conditions ： Maximum
statistic ： Aesthetic value
State definition ：dp[i][j]： Before the i Before putting the bouquet j In a bottle , The aesthetic value of the scheme with the largest aesthetic value .
The initial state ： front 0 Put a bunch of flowers in j In a vase , The aesthetic value is 0. therefore dp[0][j] = 0.

2. State transition equation

Remember that i Put a bunch of flowers in the second j The aesthetic value of a bottle is a[i][j].
aggregate ： Before the i Before putting the bouquet j A bottle
There are two ways to split sets , So there are two kinds of state transition equations .

solution 1：

Split set ： According to section i Put the bouquet into the first few bottles to split the collection

• If you put the i Put a bunch of flowers in the second j A bottle , Then we need to put the front i-1 Before putting the bouquet j-1 Get the maximum aesthetic value in bottles .dp[i][j] = dp[i-1][j-1] + a[i][j]
• If you put the i Put a bunch of flowers in the second j-1 A bottle , Then we need to put the front i-1 Before putting the bouquet j-2 Get the maximum aesthetic value in bottles .dp[i][j] = dp[i-1][j-2] + a[i][j-1]
  … If you put the i Put a bunch of flowers in the second i A bottle , Then we need to put the front i-1 Before putting the bouquet i-1 Get the maximum aesthetic value in bottles .dp[i][j] = dp[i-1][i-1] + a[i][i]
• The maximum value shall be taken in the above cases .
• Sum up ,k from i Loop to j,dp[i][j] = max(dp[i][j], dp[i-1][k-1] + a[i][k])

solution 2：

Split set ： According to section i Whether the bouquet is put into the No j Bottle to split the collection

• If you put the i Put a bunch of flowers in the second j A bottle , Then we need to put the front i-1 Before putting the bouquet j-1 Get the maximum aesthetic value in bottles .dp[i][j] = dp[i-1][j-1] + a[i][j]
• If you don't put the i Put a bunch of flowers in the second j Bottle , Then we need to put the front i Before putting the bouquet j-1 Get the maximum aesthetic value in bottles .dp[i][j] = dp[i][j-1]
• Take the maximum value in the above two cases

3. specific working means ：

1. Bottle number j Cycle range of

Because each bunch of flowers must be placed in a vase , front i Before putting the bouquet j In a bottle , The number of bottles must be greater than or equal to the number of flowers , therefore $j\ge i$.
Altogether f Bouquet of flowers v A bottle , before i Before putting the bouquet j A bottle , There is still left f-i Bouquet of flowers ,v-j A bottle , The number of remaining bottles must be greater than or equal to the number of flowers , therefore $v-j\ge f-i$, namely $j\le v-f+i$
therefore j from i Loop to v-f+i.

2. Record the plan

Set array b,b[i][j] It means that if the previous i Before putting the bouquet j A bottle , The first i The bottle where the bouquet of flowers is .
If you are sure to put the flowers in the k The bottle can get the maximum aesthetic value , Can be updated dp[i][j], Then update it at the same time b[i][j] = k.
If you put the front i Before putting the bouquet j Bottles and before putting j-1 The maximum aesthetic value a bottle can get is the same , So before i Before putting the bouquet j Bottle No i The bottle where the bouquet of flowers is , And will be before i Before putting the bouquet j-1 Bottle No i The same is true of the bottle where the bouquet is located , therefore b[i][j] = b[i][j-1].
When outputting, output in reverse order through recursive method , front i Before putting the bouquet j A bottle , The first i Bunch of flowers in b[i][j], Then, before you output i-1 Put a bunch of flowers in front b[i][j]-1 In a bottle , Then the output b[i][j].

3. Complexity

Method 2 The time complexity of the method is slightly better than that of the method 1. because f And v At most $100$,$O(n^2)$ or $O(n^3)$ The complexity can pass .
In terms of space complexity , Method 1 Can do rolling array optimization , But there's no need to , Input data and b Arrays are all $O(n^2)$ Complexity , Rolling array optimization does not reduce the overall space complexity .

【 Solution code 】

solution 1： Triple cycle

#include<bits/stdc++.h>
using namespace std;
#define N 105
int f, v, a[N][N], dp[N][N];//dp[i][j]: front i Put a bunch of flowers in front j The greatest aesthetics you can get in a vase 
int b[N][N];//b[i][j]: front i Before putting a bouquet j A bottle , The first i Which bottle is the bouquet in  
void show(int i, int j)// Before output i Before putting a bouquet j The position of each bouquet in a bottle  
{
    
	if(i == 0)
		return;
	show(i-1, b[i][j]-1);
	cout << b[i][j] << ' ';
}
int main()
{
    
    cin >> f >> v;
    for(int i = 1; i <= f; ++i)
        for(int j = 1; j <= v; ++j)
            cin >> a[i][j];
	memset(dp, 0xc0, sizeof(dp));// Initialize to negative infinity 
    for(int j = 0; j <= v; ++j)
    	dp[0][j] = 0;
	for(int i = 1; i <= f; ++i)
        for(int j = i; j <= v-f+i; ++j)
            for(int k = i; k <= j; ++k)
            {
    
        	    if(dp[i][j] < dp[i-1][k-1] + a[i][k])
        	    {
    
        	       	dp[i][j] = dp[i-1][k-1] + a[i][k];
        		    b[i][j] = k; 
        	    }
        	}
    cout << dp[f][v] << endl;
    show(f, v);
    return 0;
}

solution 2： Double cycle

#include<bits/stdc++.h>
using namespace std;
#define N 105
int f, v, a[N][N], dp[N][N];//dp[i][j]: front i Put a bunch of flowers in front j The greatest aesthetics you can get in a vase 
int b[N][N];//b[i][j]: front i Before putting a bouquet j A bottle , The first i Which bottle is the bouquet in  
void show(int i, int j)// Before output i Before putting a bouquet j The position of each bouquet in a bottle  
{
    
	if(i == 0)
		return;
	show(i-1, b[i][j]-1);
	cout << b[i][j] << ' ';
}
int main()
{
    
    cin >> f >> v;
    for(int i = 1; i <= f; ++i)
        for(int j = 1; j <= v; ++j)
            cin >> a[i][j];
	memset(dp, 0xc0, sizeof(dp));// Initialize to negative infinity 
    for(int j = 0; j <= v; ++j)
    	dp[0][j] = 0;
	for(int i = 1; i <= f; ++i)
        for(int j = i; j <= v-f+i; ++j)
        {
    
        	if(dp[i][j-1] < dp[i-1][j-1]+a[i][j])
        	{
    
        		dp[i][j] = dp[i-1][j-1]+a[i][j];
        		b[i][j] = j; 
        	}
			else
			{
    
        		dp[i][j] = dp[i][j-1];
        		b[i][j] = b[i][j-1];
        	}
        }
    cout << dp[f][v] << endl;
    show(f, v);
    return 0;
}