一些常見的優化：讀入優化,滾動數組

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 }