AtCoder Beginner Contest 189 F

这题有数学做法，但 Feecle6418 - AtCoder 提供了一种思路清奇的DP。

我们第一思路是设\(dp(i)\)为Takahashi到\(i\)时的期望步数，枚举上一次所在的位置，从\(dp(j)\)转移。

将整个流程反过来。即设\(dp(i)\)为从\(i\)开始，走到\((n,\inf)\)的期望步数。重新整理一下转移：

1. 若\(i>n\)，则\(f(i)=0\)
2. 若\(i\notin A\)，则\(f(i)=1+\frac{1}{m}\sum_{j=1}^{m} f(i+j)\)
3. 若\(i \in A\)，则\(f(i)=f(0)\)

仔细观察上面的转移，虽然它有环，但是它好像只有\(f(0)\)一个数是未知的。出现一个未知的数时我们不妨保留它，就像解方程中的\(x\)一样，看看后面能否找到登录关系。

保留\(f(0)\)之后，我们惊喜的发现，\(f(i)\)可以看成一个关于\(f(0)\)的代数式，且这个代数式的次数就是\(1\)。

我们不妨设\(f(i)=k_{i}f(0)+b_{i}\)，只转移\(k\)和\(b\)就可以了。直接转移是\(O(nm)\)的，但是可以通过前缀和优化到\(O(n+m)\)。

最终答案是\(f(0)\)。可以发现，\(f(0)\)也可以通过上面方法递推得到，故我们可以得到等式\(f(0)=k_0f(0)+b_0\)，解这个方程就可以得到\(f(0)\)。

时间复杂度为\(O(n)\)。

#include
const int maxn=100005;
int n,m,k;
int a[maxn];
struct kb {
	double k,b;
}dp[maxn],sum;
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++) {
		int pos;
		scanf("%d",&pos);
		a[pos]=1;
	}
	for(int i=1;i<=n;i++) {
		int j=i;
		while(a[j]) j++;
		if(j-i>=m) {
			puts("-1");
			return 0;
		}
	}
	dp[n]=(kb){0,0};
	sum=dp[n];
	for(int i=n-1;;i--) {
		if(a[i]) dp[i]=(kb){1,0};
		else dp[i]=(kb){sum.k/double(m),sum.b/double(m)+1};
		if(!i) break;
		sum.k+=dp[i].k,sum.b+=dp[i].b;
		if(i+m<=n) sum.k-=dp[i+m].k,sum.b-=dp[i+m].b;
	}
	double res=(-dp[0].b)/(dp[0].k-1);
	printf("%.10lf\n",res);
	return 0;
}