水题笔记_ 不等数列 [DP]

有的时候复杂度不对也是可以过的

一定要大胆尝试

懵逼的 题目

传送至 Luogu

扯淡的 题解

Noip之前XP学长出的…
当时想过一会然后就因为什么事弃掉了…
今天考试突然脑子一抽想到这道题上了…然而想错了…
然后暴零了…
考完后这道题用奇怪的方法水过去了…Emmmmm

  1. 我的做法(假的)…
    考虑在一个已经确定小于号个数的序列里插入一个更大的数构成一个更长的序列…
    发现是否能够增加一个小于号和之前序列里最大数的位置有关…
    然后得出状态和转移方程…

    1
    2
    3
    //记f[i][j]为i个数, 有j个小于号, 最大数在k的方案数,
    f[i][j][k] = sum(f[I - 1][j - 1][1 ~ k - 1]) + sum(f[I - 1][j][k - 1 ~ (I - 1)])
    sum[i][j][k] = f[i][j][k] + sum[i][j][k - 1]

    Emmmm然后就把按理说$n^2$的数据水过去了…GG

  2. 真正的做法…
    发现最大数插入的位置只可能是大于号或者小于号…
    如果插入的位置是大于号, 显然小于号个数 + 1
    如果插入的位置是小于号, 显然小于号个数不变(自己想一想为什么)
    然后就得出方程…

    1
    2
    3
    // 记f[i][j]为i个数组成的序列, 有j个小于号的方案数
    f[i][j] = f[i - 1][j] * (i - j) // 有因为原序列有j个小于号, 那么久有(i - j)个大于号可以插入, 以让小于号个数加一
    + f[i - 1][j - 1] * j // 因为原序列已经有j个小于号了, 那么有j个小于号能插入, 以让小于号个数不变

Emmmmmmmmmm…

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
记f[i][j]为i个数, 有j个小于号, 最大数在k的方案数,
f[i][j][k] = sum(f[I - 1][j - 1][1 ~ k - 1]) + sum(f[I - 1][j][k - 1 ~ (I - 1)])
Sum[i][j][k] = f[i][j][k] + sum[i][j][k - 1]

*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7ffffff)
#define LL long long
int n, wk;
LL f[MAXN][MAXN];
LL sum[2][MAXN][MAXN];
LL ans;
void solve();
int main()
{
// std::cout << "Hello, World!" << std::endl;
// freopen("c.in", "r", stdin);
// freopen("c.out", "w", stdout);
scanf("%d%d", &n, &wk);
solve();
printf("%lld", ans);
return 0;
}
/*
记f[i][j]为i个数, 有j个小于号, 最大数在k的方案数,
f[i][j][k] = sum(f[I - 1][j - 1][1 ~ k - 1]) + sum(f[I - 1][j][k - 1 ~ (I - 1)])
Sum[i][j][k] = f[i][j][k] + sum[i][j][k - 1]
*/
void solve()
{
f[0][1] = 1;
f[1][2] = 1;
sum[1][0][1] = sum[1][0][2] = 1;
sum[1][1][2] = 1;
for (int i = 3; i <= n; i++)
{
for (int j = 0; j <= min(i - 1, wk); j++)
{
for (int k = 1; k <= i; k++)
{
f[j][k] = (sum[i % 2][j][i - 1] - sum[i % 2][j][k - 1]) % 2015;
if (j > 0)
f[j][k] = (f[j][k] + sum[i % 2][j - 1][k - 1]) % 2015;
sum[(i + 1) % 2][j][k] = sum[(i + 1) % 2][j][k - 1] + f[j][k];
if (f[j][k] < 0)
{
printf("%d %d %d: %d\n", i, j, k, f[j][k]);
}
}
}
}
for (int i = 1; i <= n; i++)
{
ans += f[wk][i];
ans %= 2015;
}
}

By 完蛋的 Cansult