1、给定一个迷宫，点号表示不可行，井号表示可行。现在可以改变其中的一些井号的位置。问最少改变多少个井号可以使得从左上角到右下角存在路径。

思路：设高为$n$，宽为$m$，若井号的个数$S$小于$n+m-1$则无解。否则最多改变$n+m-1$个井号即可。令$f[x][y][k]$表示现在到达位置$(x,y)$且中途经过的点号格子数为$k$时最少经过了多少井号格子。这样进行搜索即可。搜过过程中，应该满足$k\leq n+m-1$且$k+f[x][y][k]\leq S$。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N=20;int f[N][N][N+N];int inq[N][N][N+N];int h[N][N][N+N];const int dx[]={0,0,1,-1};const int dy[]={1,-1,0,0};struct node{ int x,y,p; node(){} node(int _x,int _y,int _p): x(_x),y(_y),p(_p) {}};queue
           
             Q;void add(int x,int y,int p,int c){ if(!h[x][y][p]||f[x][y][p]>c) { h[x][y][p]=1; f[x][y][p]=c; if(!inq[x][y][p]) { inq[x][y][p]=1; Q.push(node(x,y,p)); } }}class MovingCandies{public: int minMoved(const vector
            
              t) { const int n=(int)t.size(); const int m=(int)t[0].size(); int S=0; for(int i=0;i
             
              =0&&xx
              
               =0&&yy
               
                n+m-1||pp+cc>S) continue; add(xx,yy,pp,cc); } } } for(int i=0;i<=n+m-1;++i) { if(h[n-1][m-1][i]) return i; } return -1; }};
               
              
             
            
           
          
         
        
       
      
     

　　

2、给定一个整数数组，每个数字可以被替换成字符ABC中的一个，相同的数组必须被相同的字符替换。问在被任意替换得到的所有不同的字符串中，包含子列ABC的串有多少个。

思路：一个简单的思路是分别枚举第一个A、第一个B、第一个C出现的位置，这样整个串被分成4部分，第一部分中不能出现A，第二部分不能出现B，第三部分不能出现C。这样复杂度是$O(N^{3})$。现在只枚举第一个A第一个B，然后后面字符任意的总数为$X$,不包含C的总数为$Y$，那么此次枚举对答案的贡献为$X-Y$。这样是$O(N^{2})$的复杂度。实现如代码所示。其中$f[i][j]=0$表示数字$i$可以被替换成字符$j$,$j=0$表示A，$j=1$表示B，$j=2$表示C。$tot[j]$表示有多少种数字有$j$种替换方式。

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int mod=1000000007;const int N=3005;int p[4][N];int tot[4];int f[N][4];int appears[N];class MappingABC{	void init()	{		for(int i=0;i<4;++i)		{			p[i][0]=1;			for(int j=1;j
        

t) { const int n=(int)t.size(); for(int i=0;i