Mr. Young‘s Picture Permutations

Mr. Young’s Picture Permutations

���了李煜东老师的答案。

对dp的转移有了一点别的理解。

之前都是按y总那样考虑当前状态是由那些状态转移过来的。

这道题目看算阶上的思考方式，考虑的是当前状态能够转移到那些状态。

更具体点就是说，考虑 f [ i ] [ j ] [ k ] [ l ] [ r ] f[i][j][k][l][r] f[i][j][k][l][r]我可以把这一个人放在哪一行。

f [ i + 1 ] [ j ] [ k ] [ l ] [ r ] f[i+1][j][k][l][r] f[i+1][j][k][l][r]就是把这个人放在第一行。

也就是 f [ i ] [ j ] [ k ] [ l ] [ r ] f[i][j][k][l][r] f[i][j][k][l][r]可能能转移到 f [ i + 1 ] [ j ] [ k ] [ l ] [ r ] f[i+1][j][k][l][r] f[i+1][j][k][l][r]

但是转移是需要满足条件的

也就是满足按行递增、按列递增

考虑从1~n去放，第一行一定能放这是没有问题的。

也就是第一行只需要满足 i > a[i]; } int f[a[1]+3][a[2]+3][a[3]+3][a[4]+3][a[5]+3]; memset(f,0,sizeof(f)); f[0][0][0][0][0] = 1; rep(i, 0, a[1]) { rep(j, 0, a[2]) { rep(k, 0, a[3]) { rep(l, 0, a[4]) { rep(r, 0, a[5]) { if (i j) { f[i][j + 1][k][l][r] += f[i][j][k][l][r]; } if (j > k) { f[i][j][k + 1][l][r] += f[i][j][k][l][r]; } if (k > l) { f[i][j][k][l + 1][r] += f[i][j][k][l][r]; } if (l > r) { f[i][j][k][l][r + 1] += f[i][j][k][l][r]; } } } } } } int ans = f[a[1]][a[2]][a[3]][a[4]][a[5]]; cout ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);// freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin); solve(); return 0;}