把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

HDU 4055 Number String
题目大意：
由数字1到n组成的所有排列中，问满足题目所给的n-1个字符的排列有多少个，如果第i字符是’I’表示排列中的第i-1个数是小于第i个数的。如果是‘D’，则反之。
example：“ID”对应132,231； “I?”对应123 132 231,N<= 1e4

解：

这题让我对全排列类型的题目有了新的认知，大家都已经知道了这题的做法是用dp[i][j]表示在第i个位置且最后一个位置为j时候的排列个数。关键在于，在状态上如果由于第i个位置共有i个数，有可能出现在之前的i1状态结尾出现的数也出现在了状态i2上，这个时候规定当前面的数大于等于j时将其设置为本身加一，比如原本的dp[3][3]表示的状态之一“123”转移到dp[4][2]时就变成了“1342”，从而避免了重复且覆盖了全排列。
至于为什么选择最后一个数作为j的原因当然是为了转移和无后效性，因为下一位的数字选择只和前一位有关。
转移非常好写，如果第i位是”?”，那么dp[i][j]等于dp[i-1]的前缀和，如果为”I”，则为dp[i-1]中小于j的和，如果为”D”，则为大于等于j，之所以大于等于j是因为上一位等于j的时候实际上等于j+1，注意遍历j的时候只能遍历到1-i，否则会产生重复和数位超界的情况。
最后的答案是dp[i]的和，复杂度为O(n2)。
知道解法之后这题就变得相当简单了，但是这种解决全排列的方法非常值得学习，同时也开启了线性dp的另一维度：不直接表示状态，而是通过能够决定状态的参量表示状态，也是在求方案数的dp中常见且困难的一类，关键在于想出能够表示状态且能够进行转移的参量来更好地进行状态转移，一般来讲，当要求全排列或者是n个数每个数有k种选择或者n个数里挑k个数加起来的题目大多可以转换为这种形式（或者数论形式），当然，如果n在12以内，状压也是不错的选择。

代码

代码
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

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-12
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y>>1)
#define NM 1005
#define nm 5000005
#define pi 3.1415926535897931
const ll inf = 1000000007;
using namespace std;
ll read() {
	ll x = 0, f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-')f = -1; ch = getchar(); }
	while (isdigit(ch))x = x * 10 + ch - '0', ch = getchar();
	return f * x;
}




ll d[NM][NM], ans;
int n;
char s[NM];
int main() {
	while (~scanf("%s", s + 2)) {
		n = strlen(s + 2) + 1; mem(d);
		d[1][1] = 1; ans = 0;
		inc(i, 2, n) {
			if (s[i] == 'I')
				inc(j, 1, i)d[i][j] = (d[i][j - 1] + d[i - 1][j - 1]) % inf;
			else if (s[i] == 'D')
				dec(j, i, 1)d[i][j] = (d[i][j + 1] + d[i - 1][j]) % inf;
			else {
				int t = 0;
				inc(j, 1, i)t += d[i - 1][j], t %= inf;
				inc(j, 1, i)d[i][j] = t;
			}
			inc(j,1,i)
				cout << "dp." << i << "." << j << " = " << d[i][j] << endl;
		}
		inc(i, 1, n)ans += d[n][i], ans %= inf;
		printf("%lld\n", ans);
		mem(s);
	}
	return 0;
}