《算法竞赛进阶指南》0x51线性DP（4/7）

本文主要是介绍《算法竞赛进阶指南》0x51线性DP（4/7），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A-Mr. Young's Picture Permutations

题意：有\(n\)位同学现在想把他们分成\(k\)横排，每横排的人数为\(a_1,a_2,\cdots,a_k\)，分配时应该遵循的规则是，每一横排的同学身高应该从左到右是递减的，每一竖排的同学身高应该前到后递减的，问一共有几种的分配方法，\(\sum_{i=1}^{i=k}a_i \le 30,k \le 5\)。

思路：
同学的身高不需要具体知道，直接用\(1-n\)表示身高从小到大即可
用一个多维的状态来表示排第\(i\)名学生时，\(k\)排已经排好的\(i-1\)名学生对应的状态，考虑对于第\(x\)排在这种状态下满足何种条件可以在放置一个新同学。
\(1.\)当前状态下的\(a_x <= a_i\)，即不能超过人数上限。
\(2.\)当前第\(x\)排的人数应当小于\(x-1\)排的人数，否则后面放置的身高一定更高，就没有合法的放置方案了。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 35;
int n,a[N];
ll f[N][N][N][N][N];

void solve() {
	int sum = 0;
	
	for(int i = 1;i <= n;i ++) {
		scanf("%d",&a[i]);
		sum += a[i];
	}
	
	f[0][0][0][0][0] = 1;
	for(int i = 0;i <= a[1];i ++) {
		for(int j = 0;j <= a[2];j ++) {
			for(int k = 0;k <= a[3];k ++) {
				for(int t = 0;t <= a[4];t ++) {
					for(int w = 0;w <= a[5];w ++) {
						if(i) {
							f[i][j][k][t][w] += f[i-1][j][k][t][w];
						}
						if(j && j <= i) {
							f[i][j][k][t][w] += f[i][j-1][k][t][w];
						}
						if(k && k <= j) {
							f[i][j][k][t][w] += f[i][j][k-1][t][w];
						}
						if(t && t <= k) {
							f[i][j][k][t][w] += f[i][j][k][t-1][w];
						}
						if(w && w <= t) {
							f[i][j][k][t][w] += f[i][j][k][t][w-1];
						}
					}
				}
			}
		}
	}
	printf("%lld\n",f[a[1]][a[2]][a[3]][a[4]][a[5]]);

	// memset(f,0,sizeof(f));
	for(int i = 0;i <= a[1];i ++) {
		for(int j = 0;j <= a[2];j ++) {
			for(int k = 0;k <= a[3];k ++) {
				for(int t = 0;t <= a[4];t ++) {
					for(int w = 0;w <= a[5];w ++) {
						f[i][j][k][t][w] = 0;
					}
				}
			}
		}
	}
	for(int i = 1;i <= n;i ++) a[i] = 0;
}	

int main() {
	while(~scanf("%d",&n)) {
		if(n == 0) break;
		solve();
	}
	return 0;
}

这篇关于《算法竞赛进阶指南》0x51线性DP（4/7）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！