程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdoj1584 蜘蛛牌 區間型DP

hdoj1584 蜘蛛牌 區間型DP

編輯:關於C++

題目鏈接

分析:
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;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved