给予一个包含 \(n\) 个元素的数组 \(a\)，你可以进行以下操作：
- 选择两个不同的元素 \(a_i,a_j\)（\(1 \le i,j \le n\)，\(i \ne j\)）
- 将 \(a_j\) 的值加上 \(a_i\)，并移除 \(a\) 中的第 \(i\) 个元素。
求使 \(a\) 数组严格递增（对于 \(1 \le i < n\)，有 \(a_i<a_{i+1}\)）所需的最少操作数（可以为 \(0\)）。
多组数据，\(n^2\times 2^n\times T\le 10^6,n\le 15,a_i\le 10^6\)。
\(\bigstar\texttt{Hint}\)：求操作后递增比较困难，那么求最终序列。
发现最少操作数就是最终序列最大长度，而且根据 \(n\) 的范围合理推出状态：
设 \(dp_{i,s,p}\) 完成最终序列前 \(i\) 个数的拼接，用了原来位置上 \(s\) 集合中的数，且新合并的第 \(i\) 个数在原本序列上的位置为 \(p\)，第 \(i\) 个数的最小值。
转移要求新和成的 \(i\) 与上一次和成的 \(i-1\) 满足 \(p_i>p_{i-1}\)，\(i\) 的权值大于 \(i-1\) 的权值。
这样状态数 \(\mathcal{O(n^22^n)}\)，枚举转移子集加上去后是 \(\mathcal{O(n^23^n)}\)。
输出方案？记录上一个转移过来的点即可。
#define Maxn 17
#define Maxpown 32775
int n,All,_i,_p,_s,Left,opt; // record best answer
int a[Maxn],num[Maxn],tx[Maxn],ty[Maxn];
int dp[Maxn][Maxn][Maxpown],sum[Maxpown];
pa fro[Maxn][Maxn][Maxpown];
// i,p,s 完成 i 个，base 在 p，用了 s
inline void Delete(int x)
{
for(int i=x+1;i<=Left;i++) num[i-1]=num[i];
Left--;
}
int main()
{
int T=rd();
while(T--)
{
Left=n=rd(),All=1<<n,opt=0,_i=_p=_s=0;
for(int i=1;i<=n;i++) a[i]=rd(),num[i]=i;
for(int i=0;i<All;i++) sum[i]=0;
for(int i=0;i<All;i++) for(int j=1;j<=n;j++) if((i>>(j-1))&1) sum[i]+=a[j];
for(int i=0;i<=n;i++) for(int p=0;p<=n;p++) for(int s=0;s<=All;s++)
dp[i][p][s]=inf,fro[i][p][s]=pa(0,0);
dp[0][0][0]=0;
// 推表
for(int i=0;i<n;i++) for(int p=0;p<n;p++)
for(int s=0;s<All;s++) if(dp[i][p][s]!=inf)
for(int q=p+1;q<=n;q++) if(!((s>>(q-1))&1))
{
int st=(All-1)^s^(1<<(q-1));
for(int t=st,tt;t;t=(t-1)&st)
{
tt=t|(1<<(q-1));
if(sum[tt]>dp[i][p][s] && dp[i+1][q][s|tt]>sum[tt])
dp[i+1][q][s|tt]=sum[tt],fro[i+1][q][s|tt]=pa(p,s);
}
int t=0,tt;
tt=t|(1<<(q-1));
if(sum[tt]>dp[i][p][s] && dp[i+1][q][s|tt]>sum[tt])
dp[i+1][q][s|tt]=sum[tt],fro[i+1][q][s|tt]=pa(p,s);
}
for(int i=n;i>=1;i--)
{
bool exist=false;
for(int p=1;p<=n;p++) if(dp[i][p][All-1]!=inf) exist=true,_i=i,_p=p;
if(exist) break;
}
_s=All-1;
for(int i=_i,t;i;i--)
{
pa tmp=fro[i][_p][_s];
t=_s^tmp.se,assert((t&_s)==t);
for(int j=__builtin_popcount(t)-1,tcur,tp;j;j--)
{
tcur=tp=-1;
for(int k=1;k<=Left;k++)
if(num[k]==_p) tcur=k;
else if((t>>(num[k]-1))&1) tp=k;
assert(tcur!=-1 && tp!=-1);
opt++,tx[opt]=tp,ty[opt]=tcur;
Delete(tp);
}
_p=tmp.fi,_s=tmp.se;
}
assert(opt==n-_i);
printf("%d\n",opt);
for(int i=1;i<=opt;i++) printf("%d %d\n",tx[i],ty[i]);
}
return 0;
}