BZOJ 2431 HAOI2009 在列的数目的顺序相反递归

标题效果：乞讨1~n有都布置在物种的数目相反的顺序k计划数

订购f[i][j]对于前者i原子的反向排列的数j计划数

因此，我们将第一i插入的数1~i-1该装置能生产0~i-1反向对

再就是

f[i][j]=Σf[i-1][k] (j-i+1<=k<=j)

维护前缀和就可以

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 1010

#define MOD 10000

using namespace std;

int n,k;

int f[M][M],g[M][M];

int main()

{

	int i,j;

	cin>>n>>k;

	f[0][0]=1;

	for(i=0;i<=k;i++)

		g[0][i]=1;

	for(i=1;i<=n;i++)

		for(j=0;j<=k;j++)

		{

			if(j>=i)

				f[i][j]=(g[i-1][j]-g[i-1][j-i]+MOD)%MOD;

			else

				f[i][j]=g[i-1][j];

			g[i][j]=(j?g[i][j-1]:0)+f[i][j];

			g[i][j]%=MOD;

		}

	cout<<f[n][k]<<endl;

}

BZOJ 2431 HAOI2009 在列的数目的顺序相反 递归

BZOJ 2431 HAOI2009 在列的数目的顺序相反递归