題目描述

XCX最近迷上了玩蜘蛛牌。蜘蛛牌是windowsxp操作系統(tǒng)自帶的一款紙牌游戲，游戲規(guī)則是這樣的：只能將牌拖到比它大一的牌上面（A最小，K最大），如果拖動的牌上有按順序排好的牌時，那么這些牌也跟著一起移動，游戲的目的是將所有的牌按同一花色從小到大排好。為了簡單起見，我們的游戲只有同一花色的牌，但是這樣XCX又覺得太簡單了，于是他把牌數(shù)增加到了n(1<=n<=100)，牌隨機的在一行上展開，編號從1到n，把第i號上的牌移到第j號牌上，移動距離為abs(i-j)，現(xiàn)在你要做的是求出完成游戲的最小移動距離。

輸入描述

第一行T（1<=T<=1010）代表T組數(shù)據(jù)。每組數(shù)據(jù)包括兩行，第一行是一個數(shù)字n，代表有n張牌，第二行有n個數(shù)字：為1…n的一種排列。

輸出描述

最小移動距離

樣例輸入

1 10 3 10 4 2 5 9 1 8 6 7

樣例輸出

16 題解：

采用區(qū)間動態(tài)規(guī)劃的方式，但是直接進行區(qū)間DP是沒有任何意義的，因此需要對數(shù)列進行變化一下，我們進行dp的區(qū)間[a,b]定義為高度為a到高度為b的紙牌疊加到一起，所需要的最少距離和。在一開始，我們定義數(shù)組arr[x]中存儲的是高度為x的紙牌所在的位置。那么狀態(tài)轉(zhuǎn)移就可以寫成：dp[a][b] = dp[a][j] + dp[j+1][b] + abs(arr[b]-arr[j])

代碼：

#include<bits/stdc++.h> using namespace std;int a[105],n; int dp[105][105];int main() {int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[x]=i;}for(int k=2;k<=n;k++){for(int i=1;i<=n-k+1;i++){int l=i,r=i+k-1;dp[l][r]=1e9+7;for(int j=l;j<=r-1;j++)dp[l][r]=min(dp[l][r],dp[l][j]+dp[j+1][r]+abs(a[r]-a[j]));}}printf("%d\n",dp[1][n]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的北方大学 ACM 多校训练赛 第十五场 蜘蛛牌A的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。