描述
题解
十分巧妙的一道动态规划问题,应该算是区间 dp 吧!
首先我们需要考虑,大的数应该更趋向于中间,而小的数则是在两边,所以我们不妨从大到小遍历,不断往已有序列进行插入,插入的方式决定了状态的转移,每次插入的时候我们都同时插入两个,插入方式有三种:两端、首、尾,每次插入的时候都是在已有序列紧密的挨着进行插入,这样我们就可以保证每次插入后序列都是合法的,已插入的数都大于后插入的数。那么,我们就算是找到转移方程了,但是还有限制条件,所以呢,我们每个插入的方案都要进行判断是否可以成功转移,如果可以就转移,不可以就挂。
说到初始化问题,因为我们都是成对儿插入,所以一开始就是长度为 2 的区间,那么先将所有的默认为
剩下的就没有什么可说了,看代码吧,在判断是否可以插入时最好画一下图,否则容易迷瞪……我就是迷瞪了。
很好的一道
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 72;
const int MAXK = 111;
int n, k;
char s[5];
int limit[MAXK][3];
ll dp[MAXN][MAXN];
// 0 < 1 <= 2 = 3 >= 4 > 这个部分最后画一下图,不然容易迷
bool charge(int t1, int t2, int l, int r)
{
for (int i = 0; i < k; i++)
{
if ((limit[i][0] == t1 && limit[i][1] == t2) || (limit[i][0] == t2 && limit[i][1] == t1))
{
if (limit[i][2] == 0 || limit[i][2] == 4)
{
return false;
}
}
else if (limit[i][0] == t1 || limit[i][0] == t2)
{
if (limit[i][1] >= l && limit[i][1] <= r)
{
if (limit[i][2] >= 2)
{
return false;
}
}
}
else if (limit[i][1] == t1 || limit[i][1] == t2)
{
if (limit[i][0] >= l && limit[i][0] <= r)
{
if (limit[i][2] <= 2)
{
return false;
}
}
}
}
return true;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < k;i++)
{
scanf("%d%s%d", &limit[i][0], s, &limit[i][1]);
// < <= = >= >
if (s[0] == '<' && s[1] != '=')
{
limit[i][2] = 0;
}
else if (s[0] == '<')
{
limit[i][2] = 1;
}
else if (s[0] == '=')
{
limit[i][2] = 2;
}
else if (s[0] == '>' && s[1] == '=')
{
limit[i][2] = 3;
}
else
{
limit[i][2] = 4;
}
}
for (int i = 2; i <= 2 * n; i += 2) // 区间长度
{
for (int j = 1; j <= 2 * n - i + 1; j++) // 左端点
{
int k = j + i - 1; // 右端点
dp[j][k] = 0;
if (i == 2)
{
if (charge(j, k, j + 1, k - 1))
{
dp[j][k] = 1;
}
}
else
{
if (charge(j, j + 1, j + 2, k))
{
dp[j][k] += dp[j + 2][k];
}
if (charge(k - 1, k, j, k - 2))
{
dp[j][k] += dp[j][k - 2];
}
if (charge(j, k, j + 1, k - 1))
{
dp[j][k] += dp[j + 1][k - 1];
}
}
}
}
printf("%lld\n", dp[1][2 * n]);
return 0;
}