题意

有n个数 每行填a_i个数 满足每行每列都单增 求方案数

思路

我们考虑最大值可以填到哪

如图

我们可以发现只有1,2,3这三个位置可以填

这可以分为两种情况

第一种：最后一行的最后一个（位置3）

第二种：这一行剩的比上一行多（位置1,2）

然后我们每次都填最大值 然后这个东西显然可以dp

然后就做完了

code

#include <bits/stdc++.h>
using namespace std;

long long m, arr[10], f[31][31][31][31][31];

void read() {
	cin>>m;
	if(m==0) exit(0);
	memset(arr,0,sizeof arr);
	for(long long i=1; i<=m; i++) cin>>arr[i];
}

long long dfs(long long a,long long b,long long c,long long d,long long e) {
	if(f[a][b][c][d][e]) return f[a][b][c][d][e];
	long long ans=0;
	if(a>b&&a>0) ans+=dfs(a-1,b,c,d,e);
	if(b>c&&b>0) ans+=dfs(a,b-1,c,d,e);
	if(c>d&&c>0) ans+=dfs(a,b,c-1,d,e);
	if(d>e&&d>0) ans+=dfs(a,b,c,d-1,e);
	if(e>0) ans+=dfs(a,b,c,d,e-1);
	f[a][b][c][d][e]=ans;
	return ans;
}

void compute() {
	memset(f,0,sizeof f);
	f[0][0][0][0][0]=1;
	cout<<dfs(arr[1],arr[2],arr[3],arr[4],arr[5])<<'\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	while(1) {
		read();
		compute();
	}
	return 0;
}

警示后人

注意给arr清空