题目链接：

----------------------------------------------------------------------------

刚看这题的时候感觉是区间$DP$ 然而复杂度一直停留在$O(n^3)$优化不下来

后来又瞎试了一些贪心 都在较大的数据上挂掉了

反复琢磨着大写字母和相应小写字母匹配 便想到了以前做过的括号匹配

只不过此题大写字母和小写字母的左右关系是不限制的

因此可以用一个栈来辅助贪心

如果当前加入的新的字母可以直接和栈顶匹配就直接让它们匹配

否则先丢在栈顶放着(防止做了这个匹配后使得匹配线之间的字母被限制住无法匹配)

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N = 10010; 7 char s[N]; 8 int sta[N]; 9 int ma[N], ans[N], num[N];10 int n, len, top;11 int main()12 {13     scanf("%d%s", &n, s + 1);14     len = n << 1;15     for(int i = 1; i <= len; ++i)16         if(!top || abs((int)s[sta[top - 1]] - s[i])!= 32)17             sta[top++] = i;18         else19         {20             ma[i] = sta[top - 1];21             ma[sta[top - 1]] = i;22             --top;23         }24     if(top)25     {26         puts("Impossible");27         return 0;28     }29     for(int i = 1; i <= len; ++i)30         if(s[i] < 'a')31             num[i] = num[i - 1];32         else33             num[i] = num[i - 1] + 1;34     for(int i = 1; i <= len; ++i)35         if(s[i] < 'a')36             printf("%d ", num[ma[i]]);37 }