DP summary of ACM in recent two weeks

How time flies , Two weeks have passed in the twinkling of an eye , It seems that the last time I stopped writing a blog was yesterday , Although the exam week is only two weeks away , But we still can't relax . The truth is   But the truth is , The fact is that most of my energy is still given to review , I don't feel as strong as I did at the beginning , I also want to try my best to adjust my state of mind and allocate my time reasonably .
These two weeks are still DP,DP I have studied for more than three weeks , Big head is big head , In addition to searching, it will take the teacher up to two weeks to talk about , This guy is good , It's three weeks like searching . The big head is also because it is difficult and especially useful , He can plan the optimal solution in the whole process , The most important thing is its dynamic transfer equation , Just write it out , other , It's not easy to do ‘, For example, the knapsack problem usually has a triple cycle , How to cycle , What is the order of each layer , All of these have to figure out the meaning of each layer . In the past two weeks, I have been exposed to a variety of backpacking problems , In addition to a simple and common knapsack problem, it can be solved with greed , Nothing else can be done with greed , Only use DP To find the whole best

I talked about the backpack problem for more than a week , Next, I would like to summarize what I learned in class and after class ：

01 knapsack ： For each item, there are two choices: choose or not , Seek the maximum value of the bag without exceeding the capacity of the bag . This problem can be divided into two categories , One is divisible , That's easy , Can completely apply the greedy thought , Sort directly by price / performance ratio, and then take it one by one from the beginning until it just exceeds the capacity, and then divide it to make it just full . If it cannot be divided , To use dp

Completely backpack ： Complete knapsack problem and 01 The knapsack problem is roughly the same , The only difference is the order in the loop , When traversing the capacity, it is the same as 01 Backpacks are the opposite , From small to large

Multiple backpack ： And 0-1 The difference between backpacks is the classification of items , Specify the number of pieces per item . goods i Weight of weight[i] Greater than the weight of the backpack j when , The maximum value of the backpack is dp[i][j] = dp[i-1][j], goods i Weight of weight[i] Less than or equal to the weight of the backpack j when , The maximum value of the backpack is dp[i][j] = max(dp[i-1][j - k*weight[i]] + k * value[i], dp[i-1][j])     

Pack in groups ：  Knapsack grouping and grouping 01 knapsack , Generally, three-layer circulation , Sequence is very important. The essential difference between the two is that the two layers of cycles are reversed , But the meaning is completely different , To group them, put for v=v..0 This layer of circulation must be in for be-all i Belong to the group k In addition, only one item in each group can be added to the backpack , For each group of backpacks 01 knapsack , Then turn the two or three layers of circulation upside down

In multiple loops , It is usually possible to optimize the code by reducing the dimension to reduce the complexity , And the sequence of cycles is particularly important , Like 01 Backpacks and full backpacks ,01 Backpack circulation capacity is from large capacity to small capacity , The complete knapsack cycle is from small to large ; There are also two cases in the group backpack , It is also distinguished by the sequence of cycles

Let's talk about a few questions

POJ 1384 Piggy-Bank( Completely backpack )

The question is Give the initial weight and capacity of the piggy bank , Ask for the minimum value when the piglet is full of gold coins

Different from other questions, this is to find the minimum value , The key to capacity simplicity is to find the minimum value , So you can think of initialization and dp Conditions , Be careful when initializing to infinity dp[0][0] Must be set to 0（ If you want the maximum value, the initialization should be -1）

POJ 1837 Balance（dp01 knapsack ）

There are several hooks on the left and right sides of a scale , All in all C Hook , Yes G A hook code , Find the total number of methods for hanging all hook weights on the hook to balance the balance .

You can think of the balance as a x Axis 0 Point as the horizontal axis of the equilibrium point , Arm strength = Arm length * weight , Balance when both arms are equal dp[i][j],i Is the number of weights ,j In equilibrium ,0 For balance ,j<0 To the left ,j>0 To the right , And j It can't be negative , So reset a balance point 7500 Let all the heaviest weights hang on the left . use dp[i-1][j]=num It means to put in front of i-1 You can get the status after all hook codes are hung on the Libra j The way to do this is num Time ,dp[i][j+l[k]*w[i] It means that dp[i-1][j] On the premise of this, we will go to the k Hang the... On the hook i A weight , however k]*w[i] There are many cases when the values of the products are equal , There may be more than one hook in one position at this time dp[i][j+l[k]*w[i]] It's not equal to dp[i-1][j] 了 .

P2577 [ZJOI2004] lunch                     Greed and dp combination

The main idea is n Everyone has a meal time and a meal time , Divide them into two teams . Everyone goes to dinner immediately after they get a meal , Ask for the shortest total meal time .

This requires the first use of greedy thinking , Greedy is better to think , Eat slowly and cook first to save time , First, sort according to the meal time from big to small .

Then is dp 了 ,f[i][j][k] On behalf of i personal , stay 1 The total meal time at window No j, stay 2 The total meal time at window No k, But it's obvious that this should last for a long time , So we need to optimize the code to get rid of one dimension .

f[i][j] Before presentation i personal , stay 1 The total meal time at window No j, The earliest time to finish eating . There are two situations ： Will be the first i Personal place 1 Window No ：if(j>=s[i].a) f[i][j] = min(f[i][j], max(f[i-1][j-s[i].a], j+s[i].b));f[i-1][j-s[i].a] yes i No. 1 person fetches rice + Not enough time to eat i-1 It's time for No. 1 to have dinner ; Will be the first i Personal place 2 Window No ：f[i][j] = min(f[i][j], max(f[i-1][j], sum[i]-j+s[i].b));   

poj1821 Fence【 Queue optimization linearity DP】

The main idea is k A worker painted n Road wall , Each worker can brush at most L[i] Noodles , And you must brush No S[i] Noodles , You can get it on each side P[i] The reward for . A wall can only be painted once at most .

First, according to the surface that each worker must brush s Sort , Ensure that all workers can paint after the last worker ,dp[i][j] Before presentation i A worker before painting j The maximum reward for the wall . For every worker i, You can brush or not , For each wall j, You can brush or not , therefore dp[i][j] = max(dp[i -1][j], dp[i][j -1]),dp[i][j] Another case is the second i Workers from k+1 Block brush to the j block . k+1 <= s[i] <= j, j - k<= l[i], So the equation dp[i,j]=max{dp[i-1,k]+pi*(j-k)}. loop j,k You can put i As a constant , Then you can optimize the code ,dp[i,j]=pi*j+max{dp[i-1,k]-pi*k} When j When it increases ,k The upper bound of the value of is invariant , The lower bound increases . If there are two decisions k1,k2 Satisfy dp[i-1,k1] - Pi * k1<= dp[i -1, k2] - Pi * k2 Then choose k2 Remove k1. When j Larger will be less than j-l[i] Out of the team , When querying the optimal decision , The team leader is the answer , When there is a new k When you need to join the team , Check the tonality at the end of the team , Not the best k Out of the team and new k The team .

ps1： I learned another trick when looking at a problem , The results of some questions may be much greater than long long, The maximum number is 33 position , So you can put two long long Splicing , Form a more than 33 The number of bits

Yes, this should be the last weekly blog before the holiday , Of course, I still remember the 5000 word summary , Finish this , We are going to the next summary , I will continue to take it seriously