本题核心是我们要自己选择一种放法并挖掘其性质,然后在此基础上再确定集合的表示和划分
解决DP问题要先找到答案的一些性质
我们试着构造一下答案,由于要满足同一排从左到右
递减,同一列从上到下
递减
所以我们从大到小依次安排每个同学的位置
,当前同学一定占据每排最靠左的连续若干个位置
注意我们的最终状态是放完所有的同学,与挑什么顺序放
是没有关系的,所以这种放法也能覆盖所有的方案
同时还要保证前排的人数不能多余后排
DP的核心思想是用集合来表示一类方案,然后从集合的维度来考虑状态之间的递推关系。(yxc)
再想到要根据每一排的人数去表示我们的一类集合,并由此产生我们状态的递推关系
由于排数最多是5,所以我们开一个5维数组
f[a][b][c][d][e]表示所有最后一排是a个人,倒数第二排是b个人....第一排是e个人的方案
并且有a >= b >= c >= d >= e 属性:count
状态计算:根据最后一位同学放第几排划分集合,寻找递推关系:
- 放在最后一排 f[a][b][c][d][e] = f[a-1][b][c][d][e]
- 放在倒数第二排 f[a][b][c][d][e] = f[a][b-1][c][d][e]
- .... f[a][b][c][d][e] = f[a][b][c-1][d][e]
- .... f[a][b][c][d][e] = f[a][b][c][d-1][e]
- .... f[a][b][c][d][e] = f[a][b][c][d][e-1]
将这几种情况的值加起来就是当前集合的值
像这种状态计算的时候没有加1什么的只是靠之前的状态进行递推的一定要记得初始化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 31;//注意不要开的太大
LL f[N][N][N][N][N];
int main()
{
int n;
while(cin >> n, n)
{
int id[5] = {0};//这里一定要注意初始化(因为不是所有的情况都有5排)
for(int i = 0; i < n; i ++)cin >> id[i];
memset(f,0,sizeof f);
f[0][0][0][0][0] = 1;//初始化
//从零开始才能包含到所有的方案(有的排可能没有人)
for(int a = 0; a <= id[0]; a ++)
for(int b = 0; b <= min(a,id[1]); b ++)//要保证前排的人数不能多于后排
for(int c = 0; c <= min(b,id[2]); c ++)
for(int d = 0; d <= min(c,id[3]); d ++)
for(int e = 0; e <= min(d,id[4]); e ++)
{
LL &x = f[a][b][c][d][e];
if(a && a > b)x += f[a - 1][b][c][d][e];
if(b && b > c)x += f[a][b - 1][c][d][e];
if(c && c > d)x += f[a][b][c - 1][d][e];
if(d && d > e)x += f[a][b][c][d - 1][e];
if(e)x += f[a][b][c][d][e - 1];
}
cout << f[id[0]][id[1]][id[2]][id[3]][id[4]] << endl;
}
return 0;
}