1.题意：

给你个一平板由N个矩阵组成，先Y后X，给出的点是矩阵左上角和右下角。

每个矩阵可以用一种颜色刷子粉刷，求把这平板按指定颜色全部涂色，并且该平板是竖的，当前粉刷的矩阵要保证其上面没有未粉刷的矩阵，求最少的换刷子次数？

算法：

1.根据规则建好图。

2.根据N比较少，可以用dp状态压缩或直接DFS回溯，我写的是回溯，还可以用记忆化搜索。

dp[i][j]  = c 表示最后粉刷的是第i个矩阵，已经粉刷的矩阵状态为j, 换粉刷次数为c

3. DFS 回溯

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define MAXN 1000struct Mt{ int tx,ty,bx,by,color;//左上角， 右下角 bool flag; }M[MAXN];int N, T, mp[50][50], in[50];int maxn;void build_Graph( ){ for( int i = 1; i <= N; i++) { for( int j = 1; j <= N; j++) { if( j == i ) continue; if( M[i].by == M[j].ty ) { if( !(M[j].bx < M[i].tx || M[j].tx > M[i].bx) ) { in[j]++; mp[i][j] = 1; } } } } }void color( int x ){ for( int i = 1; i <= N; i++) { if( M[i].flag || in[i] || M[i].color != x ) continue; M[i].flag = 1; for( int j = 1; j <= N; j++) { if( mp[i][j] ) in[j]--; } } }void DFS( int num ){ int i; if( num > maxn ) return; for(i = 1; i <= N; i++) { if( M[i].flag == 0 ) break; } if( i == N + 1 ) { if( num < maxn ) maxn = num; return; } int flag[30],temp[30][30],in1[30]; for( int i = 1; i <= N; i++) { if( M[i].flag || in[i] ) continue; for( int j = 1; j <= N; j++) { flag[j] = M[j].flag; in1[j] = in[j]; for( int k = 1; k <= N; k++) { temp[j][k] = mp[j][k]; } } color( M[i].color ); DFS( num + 1); for( int j = 1; j <= N; j++) { M[j].flag = flag[j]; in[j] = in1[j]; for( int k = 1; k <= N; k++) { mp[j][k] = temp[j][k]; } } } }int main( ){ scanf("%d",&T); while(T--) { scanf("%d",&N); memset(mp,0,sizeof(mp)); memset(in,0,sizeof(in)); for( int i = 1; i <= N; i++) { scanf("%d%d%d%d%d",&M[i].ty,&M[i].tx, &M[i].by,&M[i].bx, &M[i].color); M[i].flag = false; } build_Graph( ); /* for( int i = 1; i <= N; i++) printf("%d\n",in[i]); for( int i = 1; i <= N; i++) { for( int j = 1; j <= N; j++) printf("%d ",mp[i][j]); puts(""); } */ maxn = 0x7f7f7f7f; DFS( 0 ); printf("%d\n",maxn); } return 0; }
           
          
         
        
       
      

4.记忆话搜索（从网上找的别人代码，自己没写了）

#include
      
       #include
       
        #include
        
         using namespace std;struct Ret{    int x1,y1,x2,y2,c;}ret[20];#define INF 1000000000int n;int dp[15][1<<15]; //dp[i][j]表示最后一个扩展的矩形是i...已扩展的矩形状态是j需要的最少数目bool used[15];int res;bool up[20][20];void init(){     memset(used,0,sizeof(used));     res=INF;     memset(up,0,sizeof(up));     for(int i=0;i
         
          =ret[j].y2))         up[i][j]=true;     }     for(int i=0;i
          
           dp[last][use])     {       return false;     }     bool ok=false;     int now=INF;     if(count>res)     return false;     for(int i=0;i