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_i<u_{i+1}<=u_i+a_i<=u_{i+2} ui?<ui+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][i?1]+cnt)

也就是說在 j j j之前的那個點最多到 i ? 1 i-1 i?1,如果到了 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,i?1]中能到 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';
	}
}