dp选做

连续正面的可能性

题目链接

设\(f[i][j][k]\)表示i枚硬币最多连续j面朝上且最末尾有k面朝上的方法数

则：

(1) k=0 那前n-1位可以是任意数，\(f[i][j][0]=\Sigma_{k=0}^jf[i-1][j][k]\)
(2) 0<k<j 那么j枚连续朝上的面一定不出现在最后面，所以\(f[i][j][k]=f[i-1][j][k-1]\)
(3) k=j 那么有两种可能：只有最后面j位连续正面是唯一最多的，和前面已经有j位连续正面，最后面又有j位连续正面，所以\(f[i][j][j]=f[i-1][j-1][j-1]+f[i-1][j][j-1]\)

目前只想到\(O(n^3)\)的dp，看起来似乎可以\(O(n^2)\)(?)

#include <stdio.h>

int n,m,ans;
int f[200][200][200];

int main(void) { 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) f[i][0][0]=f[i][i][i]=1;
    for(int i=2;i<=n;++i)
    {
    	for(int j=1;j<i;++j)//unnecessery to check j==1 and j==i
    	{
    		for(int k=0;k<=j;++k)
    			f[i][j][0]+=f[i-1][j][k];
    		for(int k=1;k<j;++k)
    			f[i][j][k]+=f[i-1][j][k-1];
			f[i][j][j]+=f[i-1][j-1][j-1]+f[i-1][j][j-1];
		}
	}
	for(int k=0;k<=m;++k) ans+=f[n][m][k];
	printf("%d\n",ans);
	/*
	for(int i=0;i<=n;++i)
		for(int j=0;j<=i;++j)
			for(int k=0;k<=j;++k)
				printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);
	*/
	return 0;
}