时间限制: 1 Sec 内存限制: 32 MB
提交: 9 解决: 7
[提交][状态][讨论版]
题目描述
给出n个2位整数（1≤n≤10），将这n个数拼成一个长2n位长整数：y=x1 x2 x3……x2n
然后进行计算: d=│x1-x2│+│x2-x3│+….+ │x2n-1-x2n│
问题：当n个数给出之后，找出一种拼接方法，使d最小。
例如：n=3 时，三个数分别为： 26,17,34
拼接方法有：
26 17 34 d=│2-6│+│6-1│+│1-7│+│7-3│+│3-4│=20
26 34 17 d=│2-6│+│6-3│+│3-4│+│4-1│+│1-7│=17
……
17 34 26 d=│1-7│+│7-3│+│3-4│+│4-2│+│2-6│=17
其中最小d为17
输入
第一行一个整数n，第二行n个整数
输出
一个整数，即最小的d
样例输入
3 26 17 34
样例输出
17
提示
来源
2011年江苏省小学生信息学（计算机）奥赛
code
#include<iostream>
using namespace std;
int n,a[20],ans(0x7fffffff),t(0);
bool f[20]={0};
int abs(int x)
{
return x>0?x:-x;
}
void search(int t,int prev,int k)
{
int d;
if (k>=n)
{
if (t<ans) ans=t;
return ;
}
for (int i=1;i<=n;i++)
if (!f[i])
{
d=abs(a[prev]%10-a[i]/10);
t+=d;
f[i]=true;
search(t,i,k+1);
f[i]=false;
t-=d;
}
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
t+=abs(a[i]/10-a[i]%10);
}
for (int i=1;i<=n;i++)
{
f[i]=true;
search(t,i,1);
f[i]=false;
}
cout<<ans<<endl;
//system("pause");
return 0;
}
posted on 2012-08-15 22:52
龙在江湖 阅读(729)
评论(0) 编辑 收藏 引用 所属分类:
搜索