自动搬运

查看原文

来自洛谷，原作者为

	劉子颺 **

搬运于2025-08-24 21:47:18，当前版本为作者最后更新于2018-02-28 16:13:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一贪心。

引理：

对于可以取出的数字要让可达性最大。

在队首填1.

如果可达性为奇数？

那么队首是7别的是1.

坑点。

对于每个数转换为别的数，其本质是01可达性分组背包。

组：组数为n

每个组

int trans[10][10]={
	0, 4, 2, 2, 3, 2, 1, 3, 0, 1,
	0, 0, 2, 0, 0, 1, 1, 0, 0, 0,
	1, 4, 0, 1, 3, 2, 1, 3, 0, 1,
	1, 3, 1, 0, 2, 1, 1, 2, 0, 0,
	1, 2, 2, 1, 0, 1, 1, 2, 0, 0,
	1, 4, 2, 1, 2, 0, 0, 3, 0, 0,
	1, 5, 2, 2, 3, 1, 0, 4, 0, 1,
	0, 1, 1, 0, 1, 1, 1, 0, 0, 0,
	1, 5, 2, 2, 3, 2, 1, 4, 0, 1,
	1, 4, 2, 1, 2, 1, 1, 3, 0, 0
};//两两变幻代价数组。
//代价出现的必要条件：A不纯包含于B 如8->1代价为0 而 1->8 代价 为5 

由于我们需要跑一个分组背包。

这个时候写法就多了。

但是我太弱了，对于Claris大神的强行写标准分组背包望其项背。

我们写记忆化搜索

int dp[500+10][7000+10];//dp(i,j)表示从低到高位的i位要在n内使用j（既获得，取出）的火柴棍（以摆放高位）放进分组背包内
//理由：常量数组num并不能满足->腾出摆放sigma 1->n 以下所有的木棍。 
bool vis[500+10][7000+10];//记忆化 

//搜索原理：
//对于n->以下的数
//摆放的代价是由 分组背包来求
//对于n以上的->它们只会是1或7 
int dfs(int pos,int remain){
	if(remain>k)
		return INF;
	//当前可行性剪枝不存在这种情况 
	if(pos==0){//搜道0了还有摆不完的说明还是不存在这种01可达性分组背包。 
		return remain==0?0:INF;
	}
	else{
		if(vis[pos][remain])
			return dp[pos][remain];//既然搜过了就记住了。 
		vis[pos][remain]=true;//已搜 
		dp[pos][remain]=INF;//或许这种情况不存在可达性。 
		for(int i=9;i>=0;i--){//从当前位向下转换，既我要把当前位变成这个。必须for 9->1要在结果最优时输出最大的 
			int nowx=dfs(pos-1,remain+num[i]-num[s[pos]])+trans[s[pos]][i];
			dp[pos][remain]=min(dp[pos][remain],nowx);
		}
		return dp[pos][remain];//返回答案。 
	}
}

然后查询一个最大当前可剥离值。

然后贪心输出前面的答案。

	for(int i=k;i>1;i--){
		if(dfs(n,i)<=k){//这里实际上是从最高位做起。 
			int remain=i;
			if(remain&1){//贪心思想。 
				printf("7");
				remain-=3;
			}
			while(remain){
				printf("1");
				remain-=2;
			}
			dfs_print(n,i);
			return 0;
		}
	}

是的可达性背包问题是没有记录路径的于是又一个坑点来了。

查询路径。

第一，可达性可以有多种，所以必须从9查到0.

第二，我们用贪心来查。

void dfs_print(int pos,int remain){//事实上最开始只是做了一个01可达性分组背包。dfs循环找出实际结果。 
	while(pos){//例行我们从最高位做起递归打印。 
		for(int i=9;i>=0;i--){//在同样的可达性下是不是使用最高位更大更好？ 
			if(dfs(pos-1,remain+num[i]-num[s[pos]])<=k-trans[s[pos]][i]){//k-trans[s[pos][i]]表示：当前位使用辣么多木棍，注意不是释放，或许还需要拆东墙补西墙。 
				//dfs查询的就是还需要多少根，若果小于直接贪心，因为你从大往小搜。这也是为什么reverse的原因。 
				printf("%d",i);
				remain=remain+num[i]-num[s[pos]];
				k-=trans[s[pos]][i];
				pos--;
				break;
			}
		}
	}
}

于是乎就完了。

好的你也就完了。

考虑这个特殊的一批的数据：

3 1

干不了什么事，也做不了可达性背包。

于是查到答案结束代码

否则在最后输出原数。