題意：

給一個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]);}