SPOJ DP lsort方法

Question

http://www.spoj.com/problems/LSORT/这是SPOJ 一个问题它指出

你是因为对n和无重复1之间的n个数字的排列。 任务是按照升序排列该排列。还有另一个排列Q，我们从给定的排列中插入元素P.

你必须执行N个步骤来排序P.在第i步中，P有N-i + 1个元素，Q有i-1个元素，你必须从P中选择一些第x个元素（来自N-i + 1个可用元素），并将它放在Q的左边或右边。这一步的成本等于x * i。总成本是各个步骤的总和。在N步之后，Q必须是递增顺序。你的任务是降低总成本。

输入

输入文件的第一行为T（T≤10），测试用例的数目。然后描述T测试用例。每个测试用例的描述由两行组成。第一行包含一个整数N（1≤N≤1000）。第二行包含N个不同的整数，从集合{1,2，...，N}，N元件排列P.

输出

对于每组测试程序应该写一行，将含有单个整数 - 排序的最小总成本。

现在我已经想出了dp 我的递归关系表明，为了从具有值i的元素获得最优值，我将不得不在前面插入$ i $或在后面插入$ j $。

插入我在前面= DP费用第[i + 1] [j]的 +加入我在前面

成本插入Ĵ在背面= DP [的元件的成本i] [j-1]添加单元j在背面

的+ 成本，我必须采取最小的these.answer将DP [1] [n]的

for(l=1;l<=n;l++) //length of current permutation Q 
{ 
    for(i=1;i<=n-l+1;i++) //starting value of permutation Q 
    { 
    j=i+l-1; //ending value of permutation Q 
    dp[i][j]=min(dp[i+1][j]+l*xi,dp[i][j-1]+l*xj);//chosing wether to insert i at start or j at end 
    } 
} 

这里XI =元件我从置换的开始P.

和Yi =从置换的开始P.元件Ĵ的指数指数

ANS将DP [1 ] [N]

但我无法弄清楚xi和XJ 请帮

Answer 1

您可以尝试重新思考你的DP状态。

对于我来说，我会使用dp [startQ] [endQ]，其中dp [startQ] [endQ]意味着我已经花费很大的代价来对数组Q中的startQ to endQ进行排序。

如果您知道数组Q（包括整数startQ到endQ），可以通过删除/忽略startQ和endQ中的所有整数轻松地重构P的数组。

对于每个状态，DP [startQ] [ENDQ]，由于一次只能添加到前或Q的背面， DP [startQ] [ENDQ]只能是：

DP [startQ] [ENDQ-1] +添加ENDQ DP的成本[startQ-1] [ENDQ]加入startQ

与基座例是 DP的+成本[I] [I] = 0;

这些状态可以计算出来，答案可以在dp [1]] [n]找到; （假设它是一个索引）。 但是我还没有想到一个有效的方法来计算x，如果它是以自上而下的方式进行编码的，其中整个计算可以在O（N^2 log N）中使用自底向上的DP与数据结构来计算每个状态下的x。

我会留下最后的细节让你编码:)但如果需要，我可以提供更多帮助。