题目链接：

 

题意：一个n进制下的数k，其中k不会用字母，如果有A就用10代替了。求k这个数对应的，在10进制下最小的数。

分析：

本质上是把数字分成若干段使得每一段 <n 且没有前导 0

dp[i] 表示前 i 个字符划分好之后能得到的最小数。

状态枚举下一段怎么切。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 typedef long long ll; 9 const ll INF=(1LL<<62)-1;10 char s[105];11 ll dp[105];12 int main()13 {14 int n;15 scanf("%d%s",&n,s+1);16 int len=strlen(s+1);17 for(int i=0; i<=len; i++)18 dp[i]=INF;19 dp[0]=0;20 for(int i=1; i<=len; i++)21 {22 ll now=0;23 for(int j=i; j<=len; j++)24 {25 now=now*10+s[j]-'0';26 if(now>=n)break;27 if(s[i]=='0' && j>i)break;28 if(1.0*dp[i-1]*n+now>2e18)continue;29 dp[j]=min(dp[j],dp[i-1]*n+now);30 }31 }32 printf("%lld",dp[len]);33 return 0;34 }