当前位置:网站首页>Cf1453f two dimensional DP thinking

Cf1453f two dimensional DP thinking

2020-12-11 15:10:40 A kind of int_ Me

cf1453F A two-dimensional DP thinking

Original link

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[3005][3005], aa[3005];
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[1][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;
}

版权声明
本文为[A kind of int_ Me]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201211151034780w.html