本来想等写完来写总结的..........

还是没写完啊。

前面的题大多比较水....后面倒是很多难题没写。不过通过这场DP Edu，也让我发现我连背包都写不清楚....

以前对动态规划这部分有点逃避（）现在要好好练习了啊。

感谢 chy 在高一讲的dp基础技巧。

A

基础递推题啦QAQ

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN (int)(1e5+233)
#define MAXH (int)(1e4+233)
int f[MAXN],h[MAXN];
 
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&h[i]);
	f[2]=abs(h[2]-h[1]);
	for (int i=3;i<=n;i++)
		f[i]=min(abs(h[i]-h[i-1])+f[i-1],abs(h[i]-h[i-2])+f[i-2]);
//	for (int i=1;i<n;i++) printf("%d ",f[i]);
	printf("%d\n",f[n]);
	return 0;
}

B

还是基础递推...

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN (int)(1e5+233)
#define MAXH (int)(1e4+233)
int f[MAXN],h[MAXN];
 
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&h[i]);
	f[2]=abs(h[2]-h[1]);
	for (int i=3;i<=n;i++)
	{
		f[i]=abs(h[i]-h[i-1])+f[i-1];
		for (int j=i-2;j>=i-k;j--)
			if (j>0) f[i]=min(f[i],abs(h[i]-h[j])+f[j]);
	}
		
//	for (int i=1;i<n;i++) printf("%d ",f[i]);
	printf("%d\n",f[n]);
	return 0;
}

I - Coins

有\(N\)枚硬币，第\(i\)枚硬币抛出后正面朝上的概率为\(p\)，反面朝上的概率为\(1-p\)

扔完所有硬币，求正面朝上的银币数比反面朝上的银币数多的概率。

设\(f[i][j]\)表示抛\(i\)枚硬币，有\(j\)枚朝上的概率。

那么就有\(f[i][j]=f[i-1][j]*(i-p[i])+f[i-1][j-1]*p[i]\)

然后对于每个\(f[n][i]（i>=(n+1)/2）\)统计就好了对吧（

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 3021
using namespace std;
int n;
double p[MAXN],f[MAXN][MAXN];
double jt[MAXN];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
	f[1][0]=1.000-p[1]; f[1][1]=p[1];
	for (int i=2;i<=n;i++)
		for (int j=0;j<=i;j++)
			if (j>0)
				f[i][j]=f[i-1][j]*(1.00-p[i])+f[i-1][j-1]*p[i];
			else f[i][j]=f[i-1][j]*(1.00-p[i]);
	double ans=0;
	for (int j=(n+1)/2;j<=n;j++) ans+=f[n][j];//,printf("%d %d ： %lf\n",n,j,f[n][j]);
	printf("%.10lf\n",ans);
	return 0;
}

J - Sushi

设\(f[a][b][c][d]\)为剩余\(a/b/c/d\)盘\(0/1/2/3\)的期望次数

那么有

\[f[a][b][c][d]= 1 + a/n f[a][b][c][d] + b/n f[a+1][b-1][c][d] + c/n f[a][b+1][c-1][d] + d/n f[a][b][c+1][d-1] \]

\[(n-a)/n f[a][b][c][d]= 1 + b/n f[a+1][b-1][c][d] + c/n f[a][b+1][c-1][d] + d/n f[a][b][c+1][d-1] \]

\[f[a][b][c][d]= n/(n-a) + b/(n-a) f[a+1][b-1][c][d] + c/(n-a) f[a][b+1][c-1][d] + d/(n-a) f[a][b][c+1][d-1] \]

发现\(a=n-b-c-d\)

替换一下状态w

\[f[b][c][d]=n/(b+c+d) + b/(b+c+d) f[b-1][c][d] + c/(b+c+d) f[b+1][c-1][d] + d/(b+c+d) f[b][c+1][d-1] \]

发现d是递增的，拿它当最外层阶段，c当次外层

最后答案是f[sum1][sum2][sum3]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 321
using namespace std;
int n;
double f[MAXN][MAXN][MAXN];

int main()
{
	scanf("%d",&n);
	int sum1=0,sum2=0,sum3=0;
	for (int i=1,a;i<=n;i++)
	{
		scanf("%d",&a);
		if (a==1) sum1++;
		else if (a==2) sum2++;
		else sum3++;
	}
	for (int d=0;d<=sum3;d++)
		for (int c=0;c<=sum2+sum3;c++)
			for (int b=0;b<=n;b++)
			{
				if (!(b||c||d)) continue;
				f[b][c][d]=1.00*n/(1.00*b+1.00*c+1.00*d);
				if (b>=1) f[b][c][d]+=b*1.0/(b*1.0+c*1.0+d)*(double)f[b-1][c][d];
				if (c>=1&&b+1<=n) f[b][c][d]+=c*1.0/(b*1.0+c*1.0+d)*(double)f[b+1][c-1][d];
				if (d>=1&&c+1<=sum2+sum3) f[b][c][d]+=d*1.0/(b*1.0+c*1.0+d)*(double)f[b][c+1][d-1];
			}
	/*
	for (int i=0;i<=sum1;i++)
		for (int j=0;j<=sum2;j++)
			for (int k=0;k<=sum3;k++)
				printf("%d %d %d : %lf\n",i,j,k,f[i][j][k]);
	*/
	printf("%.10lf\n",f[sum1][sum2][sum3]);
	return 0;
}