傳送門
補檔計劃無題解。
這道題本來直接DP就行了，不需要用哈希表，但是一直莫名其妙的逾時，于是就交了一個表上去。（似乎沒有中間限制的輪廓線都可以交表）
代碼（輪廓線DP）：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define gc get_char
#define cs const
template<class T1,class T2>
struct Map{
static cs int magic=4001;
T1 key[magic];
T2 val[magic];
int sta[magic],top;
Map(){memset(key,-1,sizeof key);}
struct iterator{
int now;
Map *belong;
iterator(Map *a,cs int &_now):belong(a),now(_now){}
T1 key(){return belong->key[belong->sta[now]];}
T2 val(){return belong->val[belong->sta[now]];}
iterator operator++(){
++now;
return *this;
}
bool operator!=(cs iterator &b){
return now!=b.now||belong!=b.belong;
}
};
iterator begin(){return iterator(this,1);}
iterator end(){return iterator(this,top+1);}
cs T2 &operator[](cs T1 &k)cs{
int h=k%magic;
while((~key[h])&&(key[h]^k))h=(h+1)%magic;
return val[h];
}
T2 &operator[](cs T1 &k){
int h=k%magic;
while((~key[h])&&(key[h]^k))h=(h+1)%magic;
if(key[h]^k){
sta[++top]=h;
key[h]=k;
}
return val[h];
}
void clear(){
while(top){
key[sta[top]]=-1;
val[sta[top]]=0;
--top;
}
}
};
Map<int,ll> ma[2];
inline int get_state(int s,int j){
return (s&(1<<j))>>j;
}
inline int set_state(int s,int j,int b){
return (s&~(1<<j))|(b<<j);
}
inline int set_state(int s,int j,int bn,int bj){
return (s&~(3<<j))|((bn|(bj<<1))<<j);
}
int n,m,pre;
ll res[105][105];
inline void dp(){
if(m>n)swap(n,m);
ma[0].clear();ma[1].clear();pre=0;
ma[pre][0]=1;
for(int re i=0;i<n;++i)
for(int re j=0;j<m;++j){
int now=pre^1;
ma[now].clear();
for(Map<int,ll>::iterator it=ma[pre].begin();it!=ma[pre].end();++it){
int s=it.key();
ll nowans=it.val();
if(j==0)s<<=1;
int sl=get_state(s,j),su=get_state(s,j+1);
if(sl&&su)continue;
else if(!sl&&!su){
ma[now][set_state(s,j,1,0)]+=nowans;
ma[now][set_state(s,j,0,1)]+=nowans;
}
else if(!sl||!su){
ma[now][set_state(s,j,0,0)]+=nowans;
}
else assert(0);
}
pre=now;
}
cout<<ma[pre][0]<<"\n";
}
signed main(){
memset(res,-1,sizeof res);
while(~scanf("%d%d",&n,&m))dp();
return 0;
}
代碼（表）：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll res[105][105];
signed main(){
res[1][1]=res[1][1]=0;
res[1][2]=res[2][1]=1;
res[1][3]=res[3][1]=0;
res[1][4]=res[4][1]=1;
res[1][5]=res[5][1]=0;
res[1][6]=res[6][1]=1;
res[1][7]=res[7][1]=0;
res[1][8]=res[8][1]=1;
res[1][9]=res[9][1]=0;
res[1][10]=res[10][1]=1;
res[1][11]=res[11][1]=0;
res[1][12]=res[12][1]=1;
res[1][13]=res[13][1]=0;
res[1][14]=res[14][1]=1;
res[1][15]=res[15][1]=0;
res[1][16]=res[16][1]=1;
res[1][17]=res[17][1]=0;
res[1][18]=res[18][1]=1;
res[1][19]=res[19][1]=0;
res[1][20]=res[20][1]=1;
res[1][21]=res[21][1]=0;
res[1][22]=res[22][1]=1;
res[1][23]=res[23][1]=0;
res[1][24]=res[24][1]=1;
res[1][25]=res[25][1]=0;
res[1][26]=res[26][1]=1;
res[1][27]=res[27][1]=0;
res[1][28]=res[28][1]=1;
res[1][29]=res[29][1]=0;
res[1][30]=res[30][1]=1;
res[1][31]=res[31][1]=0;
res[1][32]=res[32][1]=1;
res[1][33]=res[33][1]=0;
res[1][34]=res[34][1]=1;
res[1][35]=res[35][1]=0;
res[1][36]=res[36][1]=1;
res[1][37]=res[37][1]=0;
res[1][38]=res[38][1]=1;
res[1][39]=res[39][1]=0;
res[1][40]=res[40][1]=1;
res[1][41]=res[41][1]=0;
res[1][42]=res[42][1]=1;
res[1][43]=res[43][1]=0;
res[1][44]=res[44][1]=1;
res[1][45]=res[45][1]=0;
res[1][46]=res[46][1]=1;
res[1][47]=res[47][1]=0;
res[1][48]=res[48][1]=1;
res[1][49]=res[49][1]=0;
res[1][50]=res[50][1]=1;
res[1][51]=res[51][1]=0;
res[1][52]=res[52][1]=1;
res[1][53]=res[53][1]=0;
res[1][54]=res[54][1]=1;
res[1][55]=res[55][1]=0;
res[1][56]=res[56][1]=1;
res[1][57]=res[57][1]=0;
res[1][58]=res[58][1]=1;
res[1][59]=res[59][1]=0;
res[1][60]=res[60][1]=1;
res[1][61]=res[61][1]=0;
res[1][62]=res[62][1]=1;
res[1][63]=res[63][1]=0;
res[1][64]=res[64][1]=1;
res[1][65]=res[65][1]=0;
res[1][66]=res[66][1]=1;
res[1][67]=res[67][1]=0;
res[1][68]=res[68][1]=1;
res[1][69]=res[69][1]=0;
res[1][70]=res[70][1]=1;
res[1][71]=res[71][1]=0;
res[1][72]=res[72][1]=1;
res[1][73]=res[73][1]=0;
res[1][74]=res[74][1]=1;
res[1][75]=res[75][1]=0;
res[1][76]=res[76][1]=1;
res[1][77]=res[77][1]=0;
res[1][78]=res[78][1]=1;
res[1][79]=res[79][1]=0;
res[1][80]=res[80][1]=1;
res[1][81]=res[81][1]=0;
res[1][82]=res[82][1]=1;
res[1][83]=res[83][1]=0;
res[1][84]=res[84][1]=1;
res[1][85]=res[85][1]=0;
res[1][86]=res[86][1]=1;
res[1][87]=res[87][1]=0;
res[1][88]=res[88][1]=1;
res[1][89]=res[89][1]=0;
res[1][90]=res[90][1]=1;
res[1][91]=res[91][1]=0;
res[1][92]=res[92][1]=1;
res[1][93]=res[93][1]=0;
res[1][94]=res[94][1]=1;
res[1][95]=res[95][1]=0;
res[1][96]=res[96][1]=1;
res[1][97]=res[97][1]=0;
res[1][98]=res[98][1]=1;
res[1][99]=res[99][1]=0;
res[1][100]=res[100][1]=1;
res[2][2]=res[2][2]=2;
res[2][3]=res[3][2]=3;
res[2][4]=res[4][2]=5;
res[2][5]=res[5][2]=8;
res[2][6]=res[6][2]=13;
res[2][7]=res[7][2]=21;
res[2][8]=res[8][2]=34;
res[2][9]=res[9][2]=55;
res[2][10]=res[10][2]=89;
res[2][11]=res[11][2]=144;
res[2][12]=res[12][2]=233;
res[2][13]=res[13][2]=377;
res[2][14]=res[14][2]=610;
res[2][15]=res[15][2]=987;
res[2][16]=res[16][2]=1597;
res[2][17]=res[17][2]=2584;
res[2][18]=res[18][2]=4181;
res[2][19]=res[19][2]=6765;
res[2][20]=res[20][2]=10946;
res[2][21]=res[21][2]=17711;
res[2][22]=res[22][2]=28657;
res[2][23]=res[23][2]=46368;
res[2][24]=res[24][2]=75025;
res[2][25]=res[25][2]=121393;
res[2][26]=res[26][2]=196418;
res[2][27]=res[27][2]=317811;
res[2][28]=res[28][2]=514229;
res[2][29]=res[29][2]=832040;
res[2][30]=res[30][2]=1346269;
res[2][31]=res[31][2]=2178309;
res[2][32]=res[32][2]=3524578;
res[2][33]=res[33][2]=5702887;
res[2][34]=res[34][2]=9227465;
res[2][35]=res[35][2]=14930352;
res[2][36]=res[36][2]=24157817;
res[2][37]=res[37][2]=39088169;
res[2][38]=res[38][2]=63245986;
res[2][39]=res[39][2]=102334155;
res[2][40]=res[40][2]=165580141;
res[2][41]=res[41][2]=267914296;
res[2][42]=res[42][2]=433494437;
res[2][43]=res[43][2]=701408733;
res[2][44]=res[44][2]=1134903170;
res[2][45]=res[45][2]=1836311903;
res[2][46]=res[46][2]=2971215073;
res[2][47]=res[47][2]=4807526976;
res[2][48]=res[48][2]=7778742049;
res[2][49]=res[49][2]=12586269025;
res[2][50]=res[50][2]=20365011074;
res[3][3]=res[3][3]=0;
res[3][4]=res[4][3]=11;
res[3][5]=res[5][3]=0;
res[3][6]=res[6][3]=41;
res[3][7]=res[7][3]=0;
res[3][8]=res[8][3]=153;
res[3][9]=res[9][3]=0;
res[3][10]=res[10][3]=571;
res[3][11]=res[11][3]=0;
res[3][12]=res[12][3]=2131;
res[3][13]=res[13][3]=0;
res[3][14]=res[14][3]=7953;
res[3][15]=res[15][3]=0;
res[3][16]=res[16][3]=29681;
res[3][17]=res[17][3]=0;
res[3][18]=res[18][3]=110771;
res[3][19]=res[19][3]=0;
res[3][20]=res[20][3]=413403;
res[3][21]=res[21][3]=0;
res[3][22]=res[22][3]=1542841;
res[3][23]=res[23][3]=0;
res[3][24]=res[24][3]=5757961;
res[3][25]=res[25][3]=0;
res[3][26]=res[26][3]=21489003;
res[3][27]=res[27][3]=0;
res[3][28]=res[28][3]=80198051;
res[3][29]=res[29][3]=0;
res[3][30]=res[30][3]=299303201;
res[3][31]=res[31][3]=0;
res[3][32]=res[32][3]=1117014753;
res[3][33]=res[33][3]=0;
res[4][4]=res[4][4]=36;
res[4][5]=res[5][4]=95;
res[4][6]=res[6][4]=281;
res[4][7]=res[7][4]=781;
res[4][8]=res[8][4]=2245;
res[4][9]=res[9][4]=6336;
res[4][10]=res[10][4]=18061;
res[4][11]=res[11][4]=51205;
res[4][12]=res[12][4]=145601;
res[4][13]=res[13][4]=413351;
res[4][14]=res[14][4]=1174500;
res[4][15]=res[15][4]=3335651;
res[4][16]=res[16][4]=9475901;
res[4][17]=res[17][4]=26915305;
res[4][18]=res[18][4]=76455961;
res[4][19]=res[19][4]=217172736;
res[4][20]=res[20][4]=616891945;
res[4][21]=res[21][4]=1752296281;
res[4][22]=res[22][4]=4977472781;
res[4][23]=res[23][4]=14138673395;
res[4][24]=res[24][4]=40161441636;
res[4][25]=res[25][4]=114079985111;
res[5][5]=res[5][5]=0;
res[5][6]=res[6][5]=1183;
res[5][7]=res[7][5]=0;
res[5][8]=res[8][5]=14824;
res[5][9]=res[9][5]=0;
res[5][10]=res[10][5]=185921;
res[5][11]=res[11][5]=0;
res[5][12]=res[12][5]=2332097;
res[5][13]=res[13][5]=0;
res[5][14]=res[14][5]=29253160;
res[5][15]=res[15][5]=0;
res[5][16]=res[16][5]=366944287;
res[5][17]=res[17][5]=0;
res[5][18]=res[18][5]=4602858719;
res[5][19]=res[19][5]=0;
res[5][20]=res[20][5]=57737128904;
res[6][6]=res[6][6]=6728;
res[6][7]=res[7][6]=31529;
res[6][8]=res[8][6]=167089;
res[6][9]=res[9][6]=817991;
res[6][10]=res[10][6]=4213133;
res[6][11]=res[11][6]=21001799;
res[6][12]=res[12][6]=106912793;
res[6][13]=res[13][6]=536948224;
res[6][14]=res[14][6]=2720246633;
res[6][15]=res[15][6]=13704300553;
res[6][16]=res[16][6]=69289288909;
res[7][7]=res[7][7]=0;
res[7][8]=res[8][7]=1292697;
res[7][9]=res[9][7]=0;
res[7][10]=res[10][7]=53175517;
res[7][11]=res[11][7]=0;
res[7][12]=res[12][7]=2188978117;
res[7][13]=res[13][7]=0;
res[7][14]=res[14][7]=90124167441;
res[8][8]=res[8][8]=12988816;
res[8][9]=res[9][8]=108435745;
res[8][10]=res[10][8]=1031151241;
res[8][11]=res[11][8]=8940739824;
res[8][12]=res[12][8]=82741005829;
res[9][9]=res[9][9]=0;
res[9][10]=res[10][9]=14479521761;
res[9][11]=res[11][9]=0;
res[10][10]=res[10][10]=258584046368;
int n,m;
while(~scanf("%d%d",&n,&m))cout<<res[n][m]<<"\n";
return 0;
}
![Linux-CPU優化之上下文切換[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)