AcWing 271. 【Java】杨老师的照相排列
原题链接
简单
作者:
tt2767
,
2020-01-06 23:47:49
,
所有人可见
,
阅读 975
// 状态: 问一共有多少种安排合影位置的方案? -> 每行人数为a,b,c,d,e的方案数 -> f[a][b][c][d][e]
// 转移: 按y总讲的,通常考虑最后一位的情况来做划分即 f[a][b][c][d][e] += 每行去掉最后一位的值
// 边界: f[0][0][0][0][0] = 1;
import java.util.*;
public class Main{
void run(){
while(jin.hasNext()){
int k = jin.nextInt();
if (k == 0) break;
Arrays.fill(row, 0);
for (int i = 0 ; i < k ; i++) row[i] = jin.nextInt();
for (int a = 0; a <= row[0] ; a++){
for (int b = 0 ; b <= row[1]; b++){
for (int c = 0; c <= row[2] ; c++){
for (int d = 0; d <= row[3]; d ++){
for (int e = 0; e <= row[4]; e++){
f[a][b][c][d][e] = 0;
}
}
}
}
}
f[0][0][0][0][0] = 1;
for (int a = 0; a <= row[0] ; a++){ // a<= row[0] 最大可以有row[0] 个人
for (int b = 0 ; b <= Math.min(a, row[1]); b++){
for (int c = 0; c <= Math.min(b, row[2]) ; c++){
for (int d = 0; d <= Math.min(c, row[3]); d ++){
for (int e = 0; e <= Math.min(d, row[4]); e++)
{
long v = 0;
if (a > 0 && a - 1 >= b) v += f[a-1][b][c][d][e]; // a-1 >= b a去掉最后一个人时可能和b相等
if (b > 0 && b - 1 >= c) v += f[a][b-1][c][d][e];
if (c > 0 && c - 1 >= d) v += f[a][b][c-1][d][e];
if (d > 0 && d - 1 >= e) v += f[a][b][c][d-1][e];
if (e > 0) v += f[a][b][c][d][e-1];
f[a][b][c][d][e] += v;
}
}
}
}
}
System.out.println(f[row[0]][row[1]][row[2]][row[3]][row[4]]);
}
}
int maxR = 5;
int maxP = 31;
int[] row = new int[maxR];
long[][][][][] f = new long[maxP][maxP][maxP][maxP][maxP];
Scanner jin = new Scanner(System.in);
public static void main(String[] args) throws Exception {new Main().run();}
}
厉害了,兄弟!这个题目,我的java一直没有过,你的方法过了。赞