一种区间 DP

这里是题

可以想到区间 DP。

原因

如果不是从一个区间内往外 jumping，一定要走回头路，不优，所以是区间 DP。

然而，我们以前写的区间 DP 设计对这题并不适用，无法既高效又简单的转移。

然而，我们可以在以往的 \(dp[i][j]\) 后再加一维，变成 \(dp[i][j][1/2]\)。

其中，\(dp[i][j][1]\) 表示把 \(i\sim j\) 都 jumping 一遍后停在 \(i\) 的最短路，而 \(dp[i][j][2]\) 表示把 \(i\sim j\) 都 jumping 一遍后停在 \(j\) 的最短路。

具体转移很好想，是

dp[i][j][1]=min(dp[i+1][j][1]+dis(i,i+1),dp[i+1][j][2]+dis(i,j));
dp[i][j][2]=min(dp[i][j-1][1]+dis(i,j),dp[i][j-1][2]+dis(j,j-1));

dis(i,j) 代表 \(i\) 荷叶直接 jumping 到 \(j\) 荷叶的距离。

code(thanks to luogu 398152)

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		cout<<'-';
		x=-x;
	}
	writing(x);
}
LL n;
double x[1010],y[1010],dp[1010][1010][3];
double dis(LL i,LL j)
{
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
	cin>>n;
	rep(i,1,n,1)
	{
		cin>>x[i]>>y[i];
	}
	rep(len,1,n,1)
	{
		rep(i,1,n-len+1,1)
		{
			LL j=i+len-1;
			dp[i][j][1]=min(dp[i+1][j][1]+dis(i,i+1),dp[i+1][j][2]+dis(i,j));
			dp[i][j][2]=min(dp[i][j-1][1]+dis(i,j),dp[i][j-1][2]+dis(j,j-1));
		}
	}
	printf("%.3lf\n",dp[1][n][1]);
	return 0;
}