cf 758 D Ability To Convert (dp)

题意：

给一个n和长度不超过60的数字字符串k，问将k转换为n进制能得到的最小的数字是多少。

解题思路：

比较明显要有动态规划来做，贪心会有后效性。

最开始想的是从后往前dp，每一位枚举从这一位到之后得到的不大于n的数字x再加上相应的dp值，取出最小那一位，但这样做会有后效性，因为我没有保留每个x对应得dp值，导致某些x在之后可能会更小但是我没有保留而得不到最优解。

然后看了q神代码，从前往后dp（顺序不影响正确性，但是这样做操作简单），然后对于i-1，枚举从i开始能得到的比n小的数字x，将中间的（假设用j来表示每一位）dp[j]的值都做保留，这样就能防止后效性，而得到正解了，转移方程见代码吧。

代码：

#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;const ll inf=2e18;ll dp[66];char str[66];int num[66];int main(){    int n;    scanf("%d%s", &n, str);    int i;    for(i=0; str[i]; i++)    {        num[i+1]=str[i]-'0';        dp[i+1]=inf;    }    dp[0]=0;    ll now=0;    int len=strlen(str);    for(i=1; i<=len; i++)    {        now=0;//        PRintf("%d %lld/n", i, dp[i-1]);        for(int j=i; j<=len; j++)        {            now=now*10+num[j];            if(now>=n)break;//每位数不能超过base            if(dp[i-1]>=inf/n)break;             if(num[i]==0 && j>i)break;//对于0，不能当前缀            if(dp[i-1]*n>=inf-now)continue;//            printf("%d %d/n", i, now);            dp[j]=min(dp[j], dp[i-1]*n+now);//            printf("%d %lld/n", j, dp[j]);        }//        printf("/n");    }    printf("%lld", dp[len]);}