Codeforces 758D Ability To Convert(区间DP)

时间:2021-06-07 12:54:43

题目链接:http://codeforces.com/problemset/problem/758/D

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

分析:

本质上是把数字分成若干段使得每一段 <n 且没有前导 0
dp[i] 表示前 i 个字符划分好之后能得到的最小数。
状态枚举下一段怎么切。
 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=(1LL<<)-;
char s[];
ll dp[];
int main()
{
int n;
scanf("%d%s",&n,s+);
int len=strlen(s+);
for(int i=; i<=len; i++)
dp[i]=INF;
dp[]=;
for(int i=; i<=len; i++)
{
ll now=;
for(int j=i; j<=len; j++)
{
now=now*+s[j]-'';
if(now>=n)break;
if(s[i]=='' && j>i)break;
if(1.0*dp[i-]*n+now>2e18)continue;
dp[j]=min(dp[j],dp[i-]*n+now);
}
}
printf("%lld",dp[len]);
return ;
}