CodeForces - 761C Dasha and Password （思维暴力）-白红宇

CodeForces - 761C Dasha and Password （思维暴力）

阅读量：2136 次

发布时间：2019-04-30

本文共 1438 字，大约阅读时间需要 4 分钟。

题意：给出n个字符串，每个串的初始光标都位于0（列）处，问你怎样移动光标能够在凑出密码（每个串的光标位置表示一个密码的字符，密码至少包含3种字符：数字，小写字母，特殊符号）的情况下使得移动的光标步数最小。

题解：分别把数字、字母、3种字符定义为第0类、第1类、第2类。

b[i][j] 代表当取第i个字符串，取第j类字符的最小距离，b[i][0] 代表从第i个字符串中取第0类字符，也就是数字。

然后因为数据范围比较小，处理完了之后就可以暴力枚举，i,j,k，第i个字符取0类，第j个字符取类，第k个字符取k类，算最小值。

这个题自己做的时候踩了个大坑，WA了一个小时，原因是在给b数组和ans赋最大值的时候，下意识就赋值成了INF=1e9+7，但是这样的话在最后算的时候有3个数相加，就会爆int。

记住这个教训：以后赋最大值的时候要好好想一想（有的时候数据类型用long long的赋long long型的最大值）

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define INF 10000000using namespace std;string s[100];int b[100][5];int main(){ //freopen("input.txt","r",stdin); int n,m; cin>>n>>m; for(int i=1;i<=n;++i) cin>>s[i]; for(int i=0;i<=n;++i) for(int j=0;j<5;++j) b[i][j]=INF; for(int i=1;i<=n;++i) { if(s[i][0]>='0' && s[i][0]<='9') b[i][0]=0; if(s[i][0]>='a' && s[i][0]<='z') b[i][1]=0; if(s[i][0]=='#' || s[i][0]=='*' || s[i][0]=='&') b[i][2]=0; } for(int i=1;i<=n;++i) { for(int j=1;j<=m-1;j++) { if(s[i][j]>='0' && s[i][j]<='9') b[i][0]=min(b[i][0],min(j,m-j));//因为可以左右两边走 if(s[i][j]>='a' && s[i][j]<='z') b[i][1]=min(b[i][1],min(j,m-j)); if(s[i][j]=='#' || s[i][j]=='*' || s[i][j]=='&') b[i][2]=min(b[i][2],min(j,m-j)); } } int ans=INF; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int k=1;k<=n;++k) { if(i==j || j==k || i==k) continue; ans=min(ans,b[i][0]+b[j][1]+b[k][2]); } cout<
                 
                  <