1.读入优化
我们平时所使用的scanf,cin速度都较慢,当读入的数据达到10^5规模以上时,就会开始显现劣势 而c中自带的getchar函数读入速度较快,可以用来优化数字的读入速度。
1 inline int get_num()
2 {
3 int num = 0;
4 char c;
5 bool flag = false;
6 while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
7 if (c == '-') flag = true;
8 else num = c - '0';
9 while (isdigit(c = getchar()))
10 num = num * 10 + c - '0';
11 return (flag ? -1 : 1) * num;
12 }
1 inline int read()
2 {
3 int ff=1,ret=0;
4 char s;
5 s=getchar();
6 while(s<'0'||s>'9')
7 {
8 if(s=='-') ff=-1;
9 s=getchar();
10 }
11 while(s>='0'&&s<='9')
12 {
13 ret=ret*10+s-'0';
14 s=getchar();
15 }
16 return ret;
17 }
2.滚动数组
写Dp经常需要大家开高维数组,比如F[t][i][j]。有的时候转移仅需要上一维数组,如F[t-1][i][j],而F[t-2],F[t-3]都不再有用,留着占用大量空间。我们可以用滚动数组的方式节省大量空间。 本来:int F[100][100][100]; 滚动:int F[2][100][100];
使用姿势: 维护两个数字指针Now和Pre,分别表示当前在哪一维,上一维在哪一维。也就是0和1这两个下标,哪个表示的是F[t][i][j],哪个表示的是F[t-1][i][j]。
1 //例子:
2 for (int t = 1; t <= T; t++)
3 {
4 swap(Now, Pre);/*注意这个swap用的非常精妙,不用把两个数组的值互换,仅仅互换指针就可以了。*/
5 for (int i = 1; i <= N; i++)
6 for (int j = 1; j <= M; j++)
7 F[Now][i][j] = F[Pre][i…][j…] + …;
8 }