1453 F. Even Harder(dp:高妙的状态设计)

传送门

设这条唯一的路径是 u 1 , u 2 , u 3 . . . . u_1,u_2,u_3.... u1,u2,u3....

那么有 u i u i + 1 = u i + a i = u i + 2 u_iu_{i+1}=u_i+a_i=u_{i+2} uiui+1=ui+ai=ui+2

定义 f [ i ] [ s ] f[i][s] f[i][s]为当前点在 i i i

由上一个唯一点 j j j能到 i i i,且 j j j能到的最远点是 s s s

那么枚举这个 j j j有转移方程

f [ i ] [ j + a j ] = m i n (   f [ i ] [ j + a j ] , f [ j ] [ i − 1 ] + c n t ) f[i][j+a_j]=min(\ f[i][j+a_j],f[j][i-1]+cnt) f[i][j+aj]=min( f[i][j+aj],f[j][i1]+cnt)

也就是说在 j j j之前的那个点最多到 i − 1 i-1 i1,如果到了 i i i

不仅 j j j能到 i i i, j j j之前的那个点也能到 i i i,这是不允许的

c n t cnt cnt表示 [ j + 1 , i − 1 ] [j+1,i-1] [j+1,i1]中能到 i i i的个数

因为 j j j如果通过这些点作为转折也是不被允许的

感觉是非常巧妙的 D P DP DP

#include bits/stdc++.h
using namespace std;
const int maxn = 3009;
const int inf = 1e9;
int n,T;
int f[maxn][maxn],g[maxn],a[maxn];
int main()
{
	cin  T;
	while( T-- )
	{
		cin  n;
		for(int i=1;i=n;i++)	cin  a[i];
		for(int i=2;i=n;i++)	f[1][i] = 0;
		for(int i=2;i=n;i++)
		{
			int cnt = 0;
			for(int j=i;j=n;j++)	f[i][j] = inf;
			for(int j=i-1;j=1;j--)
			{
				if( j+a[j]=i )//能从点j到i才能转移 
				{
					//从j出发,最远的点能到i-1到不了i 
					f[i][j+a[j]] = min( f[i][j+a[j]],f[j][i-1]+cnt );
					cnt++;
				}
			}
			for(int j=i+1;j=n+1;j++)	
				f[i][j] = min( f[i][j],f[i][j-1] );
		}
		cout  f[n][n]  '\n';
	}
}
最新回复(0)
/jishulzgmoPJRSj5Yw79AqDoVA9shMB1OBuWMo9aZ5IUEPWA_3D4834431
8 简首页