# Cf1453f two dimensional DP thinking

2020-12-11 15:10:40

### cf1453F A two-dimensional DP thinking

#### The question

Now we have a sequence , In the i You can walk to [i + 1, i + a[i]] Any point in the interval （ That is to say if a[i] yes 0, There's no way ）

Now we are asked to zero some positions , Make from 1 Go to the n There is only one way . Output minimum number of zeros , Make sure the input is clear .

#### Ideas

• because n<=3000, So try two-dimensional dynamic programming . First, design state is the most important step , We define \(F_{i,j}\) For from 1 To i There is only one path , And the farthest point in the path is no more than j, The minimum number of zeros in this case .
• So clearly \(F_{1,j}\) All for 0, The answer for \(F_{n,n}\)
• from 2 Start calculating , For the present i, Let's enumerate i - 1 ~ 1 All the points of , If there is \(j + a_j \ge i\), So our current \(F_{i,j + a_j}\) It's something that can be updated , The transfer equation is as follows

\[F_{i,j + a_j} = min(F_{i,j + a_j}, F_{j, i - 1} + cnt) \]

among cnt It's from j + 1 To i - 1 Of all the points , Able to reach i The number of points （ That is to say, these cnt All points need to be set to zero ）, Because we are from i - 1 To 1 The order of enumeration , therefore cnt You can record

#### AC Code

``````#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int ff, aa;
int t, n;

int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &aa[i]);
for (int j = 1; j <= n; ++j)
{
ff[i][j] = 99999999;
}
}
for (int i = 1; i <= n; ++i)
{
ff[i] = 0;
}
for (int i = 2; i <= n; ++i)
{
int cnt = 0;
for (int j = i - 1; j >= 1; --j)
{
if (j + aa[j] >= i)
{
ff[i][j + aa[j]] = min(ff[i][j + aa[j]], ff[j][i - 1] + cnt);
++cnt;
}
}
for (int j = i + 1; j <= n; ++j)
{
ff[i][j] = min(ff[i][j - 1], ff[i][j]);
}
}
printf("%d\n", ff[n][n]);
}
return 0;
}
``````

https://chowdera.com/2020/12/20201211151034780w.html