题面

求 $p(3< p \le 20)$ 根杆子，$n(0\le n \le200)$ 个圆盘的最优解（规则和普通汉诺塔一样）

解题思路

$DP$

分析

设 $f[k][i]$ 表示 $k$ 根杆子和 $i$ 个圆盘时的状态，则：

表示的意思是：

先把 $j$ 个圆盘在 $k$ 根杆子的情况下转移，再将剩下的 $i-j$ 个圆盘在 $k-1$ 根杆子的情况下转移

这样读懂了之后代码就很好写了

Warning

$ n\le 200 $，所以……高精或者py​

Code

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define ll long long
#define N 200
using namespace std;
struct node{
    int a[110],l;
    node operator+ (const node x) const{//其实重载个加法就非常方便了
        int L=max(l,x.l);node y;//L表示长度
        y.a[1]=0;
        for(int i=1;i<=L;i++) {
            y.a[i]+=a[i]+x.a[i];
            y.a[i+1]=y.a[i]/10;
            y.a[i]%=10;
        }
        if(y.a[L+1]) ++L;y.l=L;
        return y; 
    } 
}f[25][N+7],init;//init是一个单位的数，也就是1
int n,p,t;
inline node Min(register node a,register node b) {//比较大小
    if(a.l!=b.l) return (a.l<b.l)?a:b;
    register int t=a.l;
    while(a.a[t]==b.a[t]&&t) --t;
    return (a.a[t]<b.a[t])?a:b;
}
inline void Init() {//预处理一下
    int i,j,k;init.a[1]=1,init.l=1;f[3][1]=init;
    for(i=2;i<=N;i++) f[3][i]=(f[3][i-1]+f[3][i-1])+init;
    for(k=4;k<=20;k++) {
        f[k][1]=init;
        for(i=2;i<=N;i++) {
            f[k][i].l=INF;
            for(j=1;j<i;j++)
                f[k][i]=Min(f[k][i],(f[k][j]+f[k][j])+f[k-1][i-j]);
        }
    }
}
inline void Print(register int n,register int p) {
    int i;
    printf("Case %d: ",++t);
    if(!f[p][n].l) {puts("0");return;}
    for(i=f[p][n].l;i;i--)
        printf("%d",f[p][n].a[i]);
    puts("");
}
int main() {
    Init();
    while(~scanf("%d%d",&n,&p)&&p!=0) Print(n,p);//输出就好了
    return 0;
}

devil.