题解 P3205 【[HNOI2010]合唱队】
ShuYuMo
2019-10-28 20:37:59
# 这是一道DP题T_T
[https://www.luogu.org/problem/P3205](https://www.luogu.org/problem/P3205)
# 方程
- $f[i][j]$表示可以排成理想队形中的$[i, j]$, 且最后一个加进去的人被放在最左边。
- $g[i][j]$表示可以排成理想队形中的$[i, j]$, 且最后一个加进去的人被放在最右边。
- 对于$f[i][j]$，最后一个人被放在了$i$所以转移应在区间$[i + 1, j]$处。
- 对于$g[i][j]$，最后一个人被放在了$j$所以转移应在区间$[i, j - 1]$处。
所以:
- $f[i][j]$要在$f[i + 1][j]$和$g[i + 1][j]$转移过来
- $g[i][j]$要在$f[i][j - 1]$和$g[i][j - 1]$转移过来
考虑当什么时候f[i][j]会在f[i + 1][j]转移过来，
$f[i][j]$表示最后一个人放在了最左边，根据题目，最后一个人要比前面那个人矮才能放在最左边。
对于$f[i + 1][j]$来说，上一个人是$i + 1$，所以第$i$个人要矮于第$i + 1$个人，$f[i][j]$才能从$f[i + 1][j]$转移。
同理，当所以第$i$个人要矮于第$j$个人,$f[i][j]$才能从$g[i + 1][j]$转移过来。
$$f[L][R] = (f[L + 1][R] * (A[L + 1] > A[L]) + g[L + 1][R] * (A[R] > A[L]))$$
下面对于$g[i][j]$的转移同理，唯一的不同就是最后一个人被放在了最右边。
$$g[L][R] = (f[L][R - 1] * (A[L] < A[R]) + g[L][R - 1] * (A[R - 1] < A[R]))$$
区间`DP`，每个状态在转移时依赖于小区间的值，所以要保证短区间要早于长区间的处理时间。
我觉得这个题的意义还没有完成，我们从头思考，为什么要设计两个不同且相似的数组存储不同的状态。
>对从第二个人开始的每个人，如果他比前面那个人高(H较大)，那么将他插入当前队形的最右边。如果他比前面那个人矮(H较小)，那么将他插入当前队形的最左边
每次决策和最后一次放进去人和当前人的高度关系有关，所以，我们在存储和转移状态时，必须知道最后一次是那个人被放进去了。所以我们就需要两个数组`g`,`f`来记录。
哦对了~借鉴了上一篇题解才写出来，谢谢上一位同学QAQ，我再记录一下自己的心路历程
```cpp
/*!
* Copyright(c) 2019 Shu_Yu_Mo
* MIT Licensed
* Luogu: https://www.luogu.org/space/show?uid=44615
* Github: https://github.com/oldsuold/
* Gitee: https://gitee.com/Shu_Yu_Mo/
* These words were created by an amazing tool written by Shu_Yu_Mo.
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#define _R register
#define inf 0x7fffffff
using namespace std;
const int _ = 1100;
const int MOD = 19650827;
inline int read()
{
char c = getchar(); int sign = 1; int x = 0;
while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); }
while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
return x * sign;
}
int n;
int A[_];
int f[_][_];//最后一个人放在最左边边
int g[_][_];//最后一个人放在最右边边
int main()
{
n = read();
for(_R int i = 1;i <= n;i++){
A[i] = read();
}
for(_R int i = 1;i <= n;i++)
f[i][i] = 1;
for(_R int len = 2;len <= n;len++){
for(_R int L = 1;L + len - 1 <= n;L++){
int R = L + len - 1;
f[L][R] = (f[L + 1][R] * (A[L + 1] > A[L]) + g[L + 1][R] * (A[R] > A[L])) % MOD;
g[L][R] = (f[L][R - 1] * (A[L] < A[R]) + g[L][R - 1] * (A[R - 1] < A[R])) % MOD;
}
}
printf("%d", (f[1][n] + g[1][n]) % MOD);
return 0;
}
```
UDP：@lzzhhh发现一处笔误……