AcWing - 96 - 奇怪的汉诺塔 = dp

https://www.acwing.com/problem/content/98/

先考虑三个柱子的汉诺塔问题,设d[i]表示在三个柱子都可以选时,把i个塔从一个柱子移动到另一个柱子的最小移动步数。首先把n-1个塔从A移动到B,然后把n从A移动到C,再把n-1个塔从B移动到C。

d[i]=2*d[i-1]+1

当有四个柱子时,情况稍微改变,设f[i]表示在四个柱子都可以选时,把i个塔从一个柱子移动到另一个柱子的最小移动步数,但是观察到实际上最底层的n-j个塔都是要从A到D的,而其中B和C之一必然要把顶层的塔全部放上才空出另一个塔给n-j中转(当然如果只有n一个的话是不需要中转的)。

所以先把j个塔在四个柱子的情况从A移动到B,然后ACD三个塔把n-j从A移动到D,再把j个塔在四个柱子的情况从B移动到D。

f[i]=min(f[i],2*f[j]+d[n-j])

貌似可以推广到更多柱子。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int d[13], f[13];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    d[1] = 1;
    for(int i = 2; i <= 12; ++i)
        d[i] = 2 * d[i - 1] + 1;
    f[1] = 1;
    for(int i = 2; i <= 12; ++i) {
        f[i] = 1e9;
        for(int j = 1; j < i; ++j)
            f[i] = min(f[i], 2 * f[j] + d[i - j]);
    }
    for(int i = 1; i <= 12; ++i)
        printf("%d\n", f[i]);
}

AcWing - 96 - 奇怪的汉诺塔 = dp

上一篇:大内核锁 BKL


下一篇:AutoCAD.Net/C#.Net QQ群:193522571 C#判断文件夹是否已经打开