题意分析

题目背景

本题属于数学建模与动态规划问题，描述如何通过最少操作步骤将比特链上的所有环从横杆上取下。关键在于理解环的取下规则，并找到最优操作序列。

核心问题

1. 环的状态：每个环的状态为1（在横杆上）或0（已取下）。
2. 操作规则：
   • 每次只能操作一个环。
   • 环1可随时操作。
   • 环k+1的操作需满足环1到k-1已取下且环k仍在横杆上。
3. 目标：计算将所有环取下的最少操作步数。

解题思路

1. 数学建模

• 二进制思想：将环的状态视为二进制数，操作步数与二进制位权相关。
• 关键观察：环k的取下步数为$2^{k-1}$，且需考虑前置条件。

2. 动态规划预处理

• 步数计算：预处理$2^i$的值，存储为大数（避免溢出）。$$\text{cun}[i][j] = 2^i \quad \text{的大数表示}$$
• 状态转移：根据环的状态决定是否累加步数。

3. 大数处理

• 数组存储：每位数字单独存储，处理进位。
• 输出优化：从高位到低位输出结果，忽略前导零。

算法实现

代码框架

#include<iostream>
#include<cstring>
using namespace std;
int ko[1000];
int cun[1000][350];
int ans[1000];
int main()
{
	int length,i,j,sum;
	cin>>length;
	sum=0;
	for(i=0;i<length;i++)
	{
		cin>>ko[i];
		sum=sum+ko[i];
	}
	for(i=0;i<length;i++)
	{
		sum=sum-ko[i];
		if(sum%2==1)
			ko[i]=1-ko[i];
	}
	memset(cun,0,sizeof(cun));
	cun[0][0]=1;
	for(i=1;i<length;i++)
	{
		for(j=0;j<=349;j++)
		{
			cun[i][j]=cun[i-1][j]*2;
		}
		for(j=0;j<=349;j++)
		{
			if(cun[i][j]>10)
			{
				cun[i][j+1]=cun[i][j+1]+cun[i][j]/10;
				cun[i][j]=cun[i][j]%10;
			}
		}
	}
	memset(ans,0,sizeof(ans));
	for(i=0;i<length;i++)
	{
		if(ko[i]==0)
			continue;
		int carry=0;
		for(j=0;j<=349;j++)
		{
			ans[j]=ans[j]+cun[i][j]+carry;
			carry=ans[j]/10;
			ans[j]=ans[j]%10;
		}
	}
	int flag=-1;
	for(i=400;i>=0;i--)
		if(ans[i]!=0)
		{
			flag=i;
			break;
		}
	if(flag==-1)
		cout<<0;
	for(i=flag;i>=0;i--)
		cout<<ans[i];
	cout<<endl;
	/*system("pause");*/
	return 0;
}
 
 
 
 
 
		

关键步骤

1. 输入处理：读取环的状态并初始化。
2. 状态调整：根据奇偶性调整环的状态。
3. 预处理幂次：计算$2^i$的大数表示。
4. 累加步数：根据环的状态累加操作步数。
5. 结果输出：处理进位并输出大数。

复杂度分析

• 时间：$O(n^2)$，主要在大数运算和预处理。
• 空间：$O(n \cdot \text{digits})$，存储大数。