This is the 10th day of my participation in the August More Text Challenge

1936. Minimum number of steps added

Thought analysis

It looks like a simple traversal but it can cause problems when there’s too much data.

If multiple steps need to be inserted between two adjacent array elements, use the following method

for(int i = 0; i < rungs.size(a); i++){if(rungs[i] - tmp > dist){ 
        tmp += dist; ret++; i--; 
    }else{ tmp = rungs[i]; }}Copy the code

So the time complexity is O(Max(rungs)/dist), of course the time complexity is O(Max(rungs)/dist).

When timeouts are found we try to prune and reduce time complexity by using the following method

tmp = rungs[i] - rungs[i - 1];
if (tmp > dist){
    ret += tmp/dist - 1;
    if(tmp % dist ! =0)ret++;
}
Copy the code

1937 Maximum score after deduction

Thought analysis

This problem also has the characteristic of having obvious subproblems to solve the general problem. It’s easy to write code

// Pretend to have initialization code
 for(int i = 1; i < m; i++){
    for(int j = 0; j < n; j++){
        int maxt = - 1;
        for(int k = 0; k < n; k++){
            maxt = max(arr[i - 1][k] - abs(j - k),maxt); } arr[i][j] = maxt + points[i][j]; }}int maxt = - 1;
for(int i = 0; i < n; i++){
    maxt = max(maxt, arr[m - 1][i]);
}
Copy the code

But obviously the time is O(mn2), O(mn^2), O(mn2), assuming m==n, then the time is O(n3)O(n^3)O(n3), and that causes a timeout. So how do you optimize?

We can put


f [ i ] [ j ] = m a x { f [ i 1 ] [ j ] j j } + p o i n t s [ i ] [ j ] F [I] [j] = Max \ {f [I – 1] – [j ^ ‘] ∣ j – j ^ ‘∣ \} + points [I] [j].

into


f [ i ] [ j ] = m a x { f [ i 1 ] [ j ] j } + p o i n t s [ i ] [ j ] + j F [I] [j] = Max \ {f [I – 1] [j ^ ‘] – j ^ ‘\} + points [I] [j] + j

, it is obvious that this formula works only if j’ is less than j, so do the reverse calculation again and compare the two maxima as the answer.

Since f[I][k] does not exist on the right side of the expression in the formula, the two calculations can be calculated simultaneously without conflict.