G - Cut and Reorder 状压DP

我是题目链接

首先显然先一操作，然后二操作这样不会影响最终结果

一眼状压DP，选出一些a从前往后塞，f[i][j]表示选出的a状态为i，且结尾为j时最小花费

转移就看上一个状态的结尾（设为k）和当前结尾（设为j）在a里的下标是否顺着挨着（就是j=k+1），不是顺着挨着就要加个c

这样会tle

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c,ans=1e18;
int a[25],b[25],f[1<<23][23],cnt[1<<23];
int jue(int x)
{
	return x>0?x:-x;
}
signed main()
{
	cin>>n>>c;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=n;++i)cin>>b[i]; 
	for(int i=1;i<=(1<<n)-1;++i)cnt[i]=cnt[i>>1]+(i&1);
	for(int i=1;i<=(1<<n)-1;++i)
		for(int j=1;j<=n;++j)
		if(i&(1<<(j-1)))
		{
			f[i][j]=1e18;
			if(cnt[i]==1)
			{
				f[i][j]=jue(a[j]-b[1]);
			}
		}
	for(int i=1;i<=(1<<n)-1;++i)
	{
		if(cnt[i]==1)continue;
		for(int j=1;j<=n;++j)
			if(i&(1<<(j-1)))
			{
				for(int k=1;k<=n;++k)
					if(j!=k&&(i&(1<<(k-1))))
					{
						if(j==k+1)f[i][j]=min(f[i][j],f[i^(1<<(j-1))][k]+jue(a[j]-b[cnt[i]]));
						else f[i][j]=min(f[i][j],c+f[i^(1<<(j-1))][k]+jue(a[j]-b[cnt[i]]));
					}
			}
	}
	for(int i=1;i<=n;++i)ans=min(ans,f[(1<<n)-1][i]);
	cout<<ans;
	return 0;
}
/*
2 1
100 1
1 100
*/

发现k没有必要枚举，用个数组记录最小值就好啦

有人可能会说转移不是有个if条件吗，其实可以思考下，完全没影响。

这样会MLE

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c,ans=1e18;
int a[25],b[25],f[1<<22][23],minn[1<<22],cnt[1<<22];
int jue(int x)
{
	return x>0?x:-x;
}
signed main()
{
	cin>>n>>c;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=n;++i)cin>>b[i]; 
	for(int i=1;i<=(1<<n)-1;++i)cnt[i]=cnt[i>>1]+(i&1);
	for(int i=1;i<=(1<<n)-1;++i)minn[i]=1e18;
	for(int i=1;i<=(1<<n)-1;++i)
		for(int j=1;j<=n;++j)
		if(i&(1<<(j-1)))
		{
			f[i][j]=1e18;
			if(cnt[i]==1)
			{
				f[i][j]=jue(a[j]-b[1]);
				minn[i]=min(minn[i],f[i][j]);
			}
		}
	for(int i=1;i<=(1<<n)-1;++i)
	{
		if(cnt[i]==1)continue;
		for(int j=1;j<=n;++j)
			if(i&(1<<(j-1)))
			{
				if(j!=1&&(i&(1<<(j-2))))f[i][j]=min(f[i][j],f[i^(1<<(j-1))][j-1]+jue(a[j]-b[cnt[i]]));
				f[i][j]=min(f[i][j],c+minn[i^(1<<(j-1))]+jue(a[j]-b[cnt[i]]));
				minn[i]=min(minn[i],f[i][j]);
			}
	}
	cout<<minn[(1<<n)-1];
	return 0;
}
/*
2 1
100 1
2 101
*/

MLE最主要原因是f数组记录了以谁为结尾。可以改成这样，对于一个状态，枚举接下来拼接哪一连续的块（强制加个c），这样就不用记录以谁为结尾了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c,ans=1e18;
int a[25],b[25],f[1<<22],cnt[1<<22];
int jue(int x)
{
	return x>0?x:-x;
}
signed main()
{
	cin>>n>>c;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=n;++i)cin>>b[i]; 
	for(int i=1;i<=(1<<n)-1;++i)cnt[i]=cnt[i>>1]+(i&1);
	for(int i=1;i<=(1<<n)-1;++i)f[i]=1e18;
	for(int i=0;i<=(1<<n)-1;++i)
	{
		for(int l=1;l<=n;++l)
		{
			int cost=c,z=0;
			for(int r=l;r<=n;++r)
			{
				if(i&(1<<(r-1)))break;
				cost+=jue(a[r]-b[cnt[i]+r-l+1]);
				z|=1<<(r-1);
				f[i|z]=min(f[i|z],f[i]+cost);
			}
		}
	}
	cout<<f[(1<<n)-1]-c;//这里不明白为啥减去c可以试试代码下面的样例
	return 0;
}
/*
2 1
100 1
1 100
*/