题目：

蜘蛛纸牌

题目描述

游戏规则是这样的：你只能将牌移动到比它的点数大 1 的牌下面（1 最小，10 最大），移动之后，这两张牌就会并成一列。例如本来三张牌是 1 2 3，各占一列，你可以将 2 放到 3 下面（示例中用括号表示 2 在 3 的下面），则局面变成

1 空 3(2)

再将 1 移动到 2 下面，则变成

空 空 3(2 1)

如果拖动的牌上有按顺序排好的牌时，那么这些牌也跟着一起移动，游戏的目的是将所有的牌从大到小排成一列。

例如游戏局面为

2(1) 空 4(3) 空

那么可以将 21 这一列移动到 43 这一列，变为

空 空 4(3 2 1) 空

此时所有牌都在一列，游戏结束。

把位置 $i$ 的牌移到位置 $j$ 的牌上，移动距离为 $|i-j|$，其中 $|x|$ 表示 $x$ 的绝对值。

现在你要做的是求出完成游戏的最小移动距离。

输入格式

输入十个各不相同的整数 $1 \sim 10$

输出格式

输出一行一个整数表示最小移动距离

样例 #1

样例输入 #1

1 2 3 4 5 6 7 8 9 10

样例输出 #1

9

样例 #2

样例输入 #2

1 2 3 4 5 10 9 8 7 6

样例输出 #2

9

样例 #3

样例输入 #3

1 3 2 4 5 10 6 9 8 7

样例输出 #3

11

我的代码：

#include <iostream> 
#include <cmath>
using namespace std;

int a[11], dis[11][11];

int dis2(int l, int r)
{
	if (l == r)
	{
		return 0;
	}
	int ans = 2e9;
	for (int i = l; i < r; ++i)
	{
		ans = min(ans, dis2(l, i) + dis2(i + 1, r) + dis[i][r]);
	}
	return ans;
}

int main()
{
	for (int i = 0; i < 10; ++i)
	{
		cin >> a[i];
	}
	for (int i = 0; i < 10; ++i)
	{
		for (int j = 0; j < 10; ++j)
		{
			dis[i][j] = abs(a[j] - a[i]);
		}
	}
	cout << dis2(0, 9);
	
	return 0;
}

#include <iostream> 
#include <cmath>
using namespace std;

int a[11], dis[11][11];

int dis2(int l, int r)
{
	if (l == r)
	{
		return 0;
	}
	int ans = 2e9;
	for (int i = l; i < r; ++i)
	{
		ans = min(ans, dis2(l, i) + dis2(i + 1, r) + dis[i][r]);
	}
	return ans;
}

int main()
{
	for (int i = 0; i < 10; ++i)
	{
		cin >> a[i];
	}
	for (int i = 0; i < 10; ++i)
	{
		for (int j = 0; j < 10; ++j)
		{
			int maxn = 0, maxn2 = -1;
			for (int k = i + 1; k <= j; ++k)
			{
				if (a[k] > maxn)
				{
					maxn = a[k];
					maxn2 = k;
				}
			}
			dis[i][j] = abs(maxn2 - i);
		}
	}
	cout << dis2(0, 9);
	
	return 0;
}

我觉得第二份代码比较正确，但是第一份代码30分，第二份代码只有10分