題意：

給一個(gè)n和長度不超過60的數(shù)字字符串k，問將k轉(zhuǎn)換為n進(jìn)制能得到的最小的數(shù)字是多少。

解題思路：

比較明顯要有動(dòng)態(tài)規(guī)劃來做，貪心會有后效性。

最開始想的是從后往前dp，每一位枚舉從這一位到之后得到的不大于n的數(shù)字x再加上相應(yīng)的dp值，取出最小那一位，但這樣做會有后效性，因?yàn)槲覜]有保留每個(gè)x對應(yīng)得dp值，導(dǎo)致某些x在之后可能會更小但是我沒有保留而得不到最優(yōu)解。

然后看了q神代碼，從前往后dp（順序不影響正確性，但是這樣做操作簡單），然后對于i-1，枚舉從i開始能得到的比n小的數(shù)字x，將中間的（假設(shè)用j來表示每一位）dp[j]的值都做保留，這樣就能防止后效性，而得到正解了，轉(zhuǎn)移方程見代碼吧。

代碼：

#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;//每位數(shù)不能超過base            if(dp[i-1]>=inf/n)break;             if(num[i]==0 && j>i)break;//對于0，不能當(dāng)前綴            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]);}