CF1342F Make It Ascending（状压+求过程->求结果）

CF1342F Make It Ascending

给予一个包含 \(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;
}

原文地址：http://www.cnblogs.com/EricQian/p/16852026.html