CodeforcesRound#392(Div.2)D.AbilityToConvert

题目链接：点击打开链接

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

题目思路：

思路有两种。

第一种比较麻烦但容易想到的贪心：（从后往前）

从后往前低位贪心选取的数尽量大。

要注意数字中有0的时候，如果不能和后面加前面不为0的数组在一起，将后面先组起来，然后在判断当前0时候能和前面不为0的组，不能单独成一位。

第二种代码极其简单方便，但需要认真思考，用dp的思路。（从前往后推）

本质上是把数字分成若干段使得每一段 

以下用的是第二种的代码：

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll INF=(1LL<<62)-1;
char s[105];
ll dp[105];
int main()
{
int n;
scanf("%d%s",&n,s+1);
int len=strlen(s+1);
for(int i=0; i<=len; i++)
dp[i]=INF;
dp[0]=0;
for(int i=1; i<=len; i++)
{
ll now=0;
for(int j=i; j<=len; j++)
{
now=now*10+s[j]-'0';
if(now>=n)break;
if(s[i]=='0' && j>i)break;//不能有前导0
if(1.0*dp[i-1]*n+now>2e18)continue;
dp[j]=min(dp[j],dp[i-1]*n+now);
}
}
printf("%I64d",dp[len]);
return 0;
}