BZOJ 3029 守卫者的挑战

发表于 | 更新于

Link

Solution

受期望的影响，我设计出状态f[i][v][l]f[i][v][l]表示从第ii个开始处理，有剩余空间vv，还需完成ll个任务，能做到的概率。 显然，从后往前DP，f[i][v][l]=p[i]×f[i+1][v+a[i]][l+1]+(1−p[i])×f[i+1][v][l]f[i][v][l]=p[i]\times f[i+1][v+a[i]][l+1]+(1-p[i])\times f[i+1][v][l]。 然后发现DP出的结果上天了——远远超过1。。。 仔细思考，我的边界设置的是所有f[n][v][0]=1f[n][v][0]=1，其实是包含了很多不合法状态的。 我的答案来自∑v+vinit>0f[1][v][0]\sum_{v+v_{init}>0}f[1][v][0]，就是有很多是从不合法的状态转移过来的。 于是Orz Po姐。 从前往后DP。解决。

Tips

一定要从合法状态开始推啊！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=200+1;
int main()
{
	static double f[MAXN][MAXN<<1][MAXN],p[MAXN];
	static int a[MAXN];
	//freopen("input","r",stdin);
	int n,lim,iv;red(n),red(lim),red(iv);
	for(int i=1;i<=n;i++) scanf("%lf",&p[i]),p[i]/=(double)100;
	for(int i=1;i<=n;i++) red(a[i]);
	#define conv(x) ( x<-n? 0 : (x>n ? 2*n : x+n ) )
	double ANS=0;
	f[0][conv(iv)][0]=1;
	for(int i=1;i<=n;i++)
		for(int v=-n;v<=n;v++)
			for(int l=0;l<=n;l++)
			{
				f[i][conv(v+a[i])][l+1]+=p[i]*f[i-1][conv(v)][l];
				f[i][conv(v)][l]+=(1-p[i])*f[i-1][conv(v)][l];
			}
	for(int v=0;v<=n;v++)
		for(int l=lim;l<=n;l++)
			ANS+=f[n][conv(v)][l];
	printf("%.6lf\n",ANS);
	return 0;
}