Necessary and sufficient conditions for monotonicity of decision making
For two decision points, if at I, the large decision point is better than the small decision point, then at [i+1,n], the large decision point is better than the small decision point
When proving, there is no need for mathematical proof, and it is enough to prove that the cost array is "convex" by typing a table
J < j + 1 < = I < I + 1 prove cost array
Cross less than include
---------------------------------------------------------------------------------------------------------------------------------
1D dynamic programming optimization
Preliminary optimization of 1D/1D dynamic programming
The so-called 1D/1D dynamic programming refers to the dynamic programming equation with the number of states O(n) and the decision quantity of each state O(n).
The time complexity of direct solution is O(n2), but most of these equations can be solved through reasonable organization and optimization
To optimize the time complexity of O(nlogn) and even O(n). Here I want to talk about some of the more preliminary classic
Understanding of optimization methods.
In this paper, we don't want to prove and deduce too much. We mainly want to explain the establishment, transformation and solution methods of classical models.
Due to my limited knowledge and level, if there are any mistakes and omissions, please make more corrections. In addition, also
I hope Daniel will introduce more in-depth things about dynamic programming optimization to us.
In this paper, two ways are used to represent a function: f(x) and f[x]. The function value expressed in square brackets can be before planning
All are calculated (constants), and the function values expressed in parentheses must be calculated (variables) in the planning process. Whatever it is
Once the function value is determined, it will not be changed in future calculations.
We always think along the idea of "what is the optimal decision of f(x)". Let's change another angle,
For a calculated state f(j), "what states can be updated by f(j)". In this way, every step of the process
Some state decisions may not be optimal, but when the algorithm ends, the decisions corresponding to all States must be optimal
of
At first, only the function value of f(1) is calculated, so the current optimal decision of all States is 1.
111111111111111111111111111111111111111111111111111111111111111
Now, obviously, the value of f(2) has been determined: its most promising decision can only be 1. We update this decision with decision 2
Watch. Due to the monotony of decision-making, we know that the new decision table can only have this form:
111111111111111111111111111111222222222222222222222222222222
This means that we can use dichotomy to find the "turning point", because if at a point x, if decision 2 is more important
Good, then all States larger than x are better than decision 2; If decision 1 is better on x, then all States smaller than x are
Decision 1 is better.
Now that both decision 1 and decision 2 have been updated, f(3) has been determined. Now use decision 3 to update all States.
According to the monotonicity of decision-making, the current decision table can only have the following two types:
11111111111111111111111111111111122222222222222222233333333333
1111111111111111111111111333333333333333333333333333333333333
Such a decision means that it will never happen:
111111111333333333333333333322222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222.
Then, our update algorithm is:
1. Check whether decision 3 is better at point B of the interval [b,e] of decision 2. If so, discard all decision 2 and replace it
Interval allocation decision 3; If not, find the turning point in the interval [b,e] of decision 2.
2. If the answer to question 1 is "yes", examine decision 1 in the same way.
At this stage, I believe that the implementation algorithm of decision monotonicity has been clear: using a stack to maintain data accounts for
Each element holds the starting and ending positions of a decision. Obviously, these positions are connected and incremented in turn. When inserting
When entering a new decision, scan the stack from back to front. For each old decision, do two things:
1. If the new decision is better at the starting point of the old decision, withdraw from the stack, abandon the old decision in full, and merge its interval into
In the new decision, continue to scan the next decision.
2. If the old decision-making is the starting point, the old decision-making must be at the old turning point; Binary search
Then the new decision goes into the stack and ends.
Since a decision will not enter after it is out of the stack, the sharing time is O(1), but due to the existence of binary search,
Therefore, the time complexity of the whole algorithm is O(nlogn).
noi2009a poet small G corresponding 1D dynamic programming optimization analysis
1 //Don't submit it to Luogu. There is a problem with the data of Luogu. Go to codeVs
2 #include<cstdio>
3 #include<cstring>
4 #define ll long double
5 //node[i] stands for I, in which l stands for the starting point of decision-making, r stands for the end point of decision-making, and p is the value of decision-making
6 struct node{int l,r,p;}q[100100];
7 #define MAX 1000000000000000000LL
8 #define N 100100
9 ll sum[N],f[N];
10 int n,l,p,T;
11 char ch[35];
12 //Find the function of | y|^p
13 ll pow(ll y){
14 if(y<0)y=-y;
15 ll ans=1;
16 for (int i=1;i<=p;i++) ans*=y;
17 return ans;
18 }
19 //Computing uncoordinated scheduling
20 ll calc(int x,int y){
21 return f[x]+pow(sum[y]-sum[x]+(y-x-1)-l);
22 }
23 //Binary search to find the turning point of decision-making
24 //node represents the old decision point and x represents the value of the new decision point
25 //This function is to find the value of the new decision point in the range of the old decision point
26 int find(node t,int x){
27 int l=t.l,r=t.r;
28 while(l<=r){//When the head is less than or equal to the tail, that is, there are still numbers to find
29 //mid = (head + tail) / 2
30 int mid=(l+r)>>1;
31 //In the case of less than, that is, the new decision-making point is more, we should continue to expand the starting point of the new decision-making point,
32 //Until the old decision-making point is better
33 if (calc(x,mid)<=calc(t.p,mid)) r=mid-1;
34 //Greater than, that is, when the old decision point is better, we will search the starting point of the scope of the new decision point later
35 else l=mid+1;
36 }
37 //Return header
38 return l;
39 }
40
41 void dp(){
42 //Simulate the stack with an array, with the head set to 1 and the tail set to 0
43 int head=1,tail=0;
44 //Put the first decision into the stack. The starting point of decision 1 is 0, the ending point is n, and the initial value of the decision is set to 0, because the initial decision is 0
45 q[++tail]=(node){0,n,0};
46 //Find f[i]
47 for (int i=1;i<=n;i++){
48 //If the end point of the decision action on the stack head node is less than i, it means that the decision can no longer act on i, so we need to replace the decision
49 //Head < = tail the head of the stack is less than or equal to the tail, indicating that there are new decisions in the stack, so replace them with new decisions
50 //Because of head + +, the head node points to the new decision
51 if(q[head].r<i&&head<=tail) head++;
52 //The value of f[i] is calculated by a new decision that can act on the position of I, so the calculated value of f[i] is the optimal value
53 f[i]=calc(q[head].p,i);
54 //calc(i,n) means to calculate the value of f[n] through the decision with value i
55 //calc(q[tail].p,n) means to pass the old decision Q [tail] P to calculate the value of f[n]
56 //Calc (i, n) < = Calc (Q [tail]. P, n) means that the decision with the value of i is better than the old decision, so we can go to the next step
57 //Otherwise, if the old decision is better, we don't need to change the decision
58
59 //Every calculated f[i] will make I a new decision, because I have the value of f[i],
60 //So I can use the value of f[i] to help calculate other F [k] (k > I), so f[i] is a new decision
61
62 /*
63 For example, in our example 1, when i==3, we pass Q [head] The decision of P = 2 calculates f[3]
64 For example, n here is 4. If Calc (3,4) < = Calc (2,4), the new decision with a value of 3 is better,
65 We need to find out the action range of decision 3 in the action range of decision 2
66 */
67
68
69 //If the new decision is better, find out the scope of the new decision
70 //Determine the end point of the new decision point
71 if (calc(i,n)<=calc(q[tail].p,n)){
72 //If the head of the stack is less than or equal to the tail, head < = tail, it indicates that there are elements in the stack
73 //calc(q[tail].p,q[tail].l) indicates the starting point of using the decision value of the old decision point to decide the old decision point
74 //calc(i,q[tail].l) uses the new decision point to decide the starting point of the old decision point
75 //If the latter is smaller than the former, it means that the new decision is better, then we should look for the decision-making scope of the new decision-making point in a broader scope
76 //In other words, when the action scope of the new decision point covers the old decision point, we should look for the action orientation of the new decision point in the old decision point
77 while(head<=tail&&calc(q[tail].p,q[tail].l)>=calc(i,q[tail].l)) tail--;
78 //Head > tail indicates that the stack is empty, which means that the new decision point is the best, so put the new decision point into the stack
79 if(head>tail)q[++tail]=(node){i,n,i};
80 else{
81 //Otherwise, we have to find the scope of the new decision-making point
82 //x returns the starting point of the new decision point range
83 int x=find(q[tail],i);
84 //The tail of the old decision point is set to x-1
85 q[tail].r=x-1;
86 //Stack new decision points
87 q[++tail]=(node){x,n,i};
88 }
89 }
90 }
91 }
92
93 int main(){
94 scanf("%d",&T);
95 while(T--){
96 scanf("%d%d%d",&n,&l,&p);
97 for (int i=1;i<=n;i++) scanf("%s",ch),sum[i]=sum[i-1]+strlen(ch);
98 dp();
99 if(f[n]>MAX)
100 puts("Too hard to arrange");
101 else
102 printf("%lld\n",(long long)f[n]);
103 puts("--------------------");
104 }
105 return 0;
106 }