hdoj1584 蜘蛛牌 區間型DP

hdoj1584 蜘蛛牌 區間型DP

題目鏈接

分析：
f[i][j] 表示 把一串牌 牌 i 到 j 摞為一摞 時花費最少的步數。
d[i][j] 表示把牌 i 挪到牌 j 上時需要走的步數（最初給的狀態）。
以一串牌 3~8 為例， 我們需要把牌 3 放到牌 4 上 ， 而在最優的移動方案下， 牌 4 的位置不確定， 所以我們枚舉牌 4 所在的位置（因為一共10張牌， 枚舉是可以的）， 這樣得出狀態轉移方程： f[3][8] = min(f[3][8], f[4][k] + f[k][8] + d[3][k]); ( 4 <= k <= 8)。 f[i][j] = min (f[i][j], f[i+1][k] + f[k][j] + d[i][k]);

舉個例子： 牌的初始順序為 1， 4， 6， 8， 3， 2， 5， 7， 9， 10
求f[1][4] 時。 最有順序應該是 ： 先把牌 2 移到 牌 3 上， 把牌 2~3 移到牌 4 上。 最後 把牌 1 移到 牌 2 上。 而此時牌 2 已經在 牌4 的位置上了。（f[1][4] = f[2][4] + f[4][4] + d[1][4] = 5）。

#include
#include
#include
#include
#include
#include
using namespace std;

int t, a[15], d[15][15], f[15][15];
void dp()
{
    for(int i = 0; i < 10; i++)//所求的區間不斷增大， 先求距離小的區間， 得出最優子問題解
    {
        for(int j = 1; j <= 10; j++)//所求將一串牌 j 到 i+j 摞成一摞時最小步數。 
        {
            if(i + j > 10) continue;
            for(int k = j + 1; k <= i + j; k++)//枚舉上一張牌所在的位置
                f[j][i+j] = min(f[j][i+j], f[j+1][k] + f[k][i+j] + d[j][k]);
        }
    }
}
void Init()
{
    for(int i = 1; i <= 10; i++)
        scanf("%d", &a[i]);
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= 10; i++)//將所有距離預處理下
    {
        for(int j = 1; j <= 10; j++)
        {
            int x = a[i], y = a[j];
            d[x][y] = abs(i - j);
            d[y][x] = d[x][y];
        }
    }
}
int main()
{
    cin >> t;
    while(t--)
    {
        for(int i = 1; i <= 10; i++)
        {
            for(int j = 1; j <= 10; j++)
            {
                f[i][j] = 10e8;
                if(i == j)
                    f[i][j] = 0;
            }
        }
        Init();
        dp();
        printf("%d\n", f[1][10]);
    }
    return 0;
}