这种递归算法有什么问题？

Question

问题语句：

n元素排列是与集合{1，2，...，n}不同数字的N元素序列。例如，序列2,1,4,5,3是5个元素排列。P是N元素排列。您的任务是按升序排序P。但是，因为这很简单，所以我有一个新规则。您有两个序列P和Q。P是N元素排列，Q最初是空的，并通过对P进行排序（即Q = 1、2、3，...，n）形成。您必须实现n个步骤才能对P进行分类。在第i-thev中，P具有n-i 1个元素，Q具有I-1元素，您必须选择一些X-the元素（来自N-I P的1个元素），将其放在Q的左侧或右侧。此步骤的成本等于x * i。总成本是单个步骤的成本总和。n步骤之后，q必须是升序序列。您的任务是最大程度地减少总成本。

输入

输入文件的第一行是t（t≤10），即测试用例的数量。然后随后对t测试案例的描述。每个测试案例的描述由两行组成。第一行包含一个单个整数n（1≤n≤1000）。第二行包含n个不同的整数与集合{1，2，..，n}，n元素置换p。

输出

对于每个测试案例，您的程序应编写一行，其中包含一个整数 - 排序的最低总成本。

输入：144 1 3 2

输出：15

我的解决方案：

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int sz;
int n[1001];
map<int,int>pos;
int solve(int i,int a,int b){
if(a==-1&&b==sz) //if all the elements have been moved 
    return 0;
if(i>sz)
    return INT_MAX;
    int ret = INT_MAX;
    if(a>=0) //select the element from left
        ret = min(ret,solve(i+1,a-1,b)+((i+1)*pos[n[a]]));
    if(b<sz) //select the element from right
        ret = min(ret,solve(i+1,a,b+1)+((i+1)*pos[n[b]]));
return ret;
}
int main()
{
   int t;
   cin>>t;
   while(t--){
        cin>>sz;
   for(int i=0;i<sz;i++){
    int x;
    cin>>x;
    n[i] = x; //value
    pos[x] = i+1; //position of elements of array before sorting
   }
   sort(n,n+sz); //sorting the array
   int ret = INT_MAX;
   for(int i=0;i<sz;i++)  
     ret= min(ret,solve(0,i,i+1));
             cout << ret << endl;
        }
    return 0;
}

这返回错误的答案。我的方法怎么了？如何修复？

Answer 1

一个问题是，您是根据POS [n [a]]计算成本。

pos [n [a]]返回原始数组中的位置，但成本应基于当前数组p中的位置（即，将某些元素移至q）。

例如，如果p最初是{4,1,2}，则2的位置为x == 3，但是将p降低到{1,2}后，则2的位置为x == 2。