2 条题解

  • 0
    @ 2026-6-3 20:42:50

    能写出这种代码,我的思维真不是正常人能达到的高度了

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    int n,a,b,c,l[10];
    signed main()
    {
    	cin>>n>>a>>b>>c;int ans=(1ll<<30);
    	for(int i=1;i<=n;i++)cin>>l[i];
    	for(int S1=1;S1<(1<<n);S1++)
    	{
    		int s1=0,cnt1=0,sum=0;
    		for(int i=1;i<=n;i++)
    			if(S1&(1<<i-1))s1+=l[i],cnt1++;
    		sum+=abs(a-s1)+(cnt1-1)*10;
    		for(int S2=1;S2<(1<<n);S2++)if((S1&S2)==0)
    		{
    			int s2=0,cnt2=0;
    			for(int j=1;j<=n;j++)
    				if(S2&(1<<j-1))s2+=l[j],cnt2++;
    			sum+=abs(b-s2)+(cnt2-1)*10;
    			for(int S3=1;S3<(1<<n);S3++)if(((S2&S3)==0)&&((S1&S3)==0))
    			{
    				int s3=0,cnt3=0;
    				for(int k=1;k<=n;k++)
    					if(S3&(1<<k-1))s3+=l[k],cnt3++;
    				sum+=abs(c-s3)+(cnt3-1)*10;
    				ans=min(ans,sum);
    				sum-=abs(c-s3)+(cnt3-1)*10;
    			}
    			sum-=abs(b-s2)+(cnt2-1)*10;
    		}
    		sum-=abs(a-s1)+(cnt1-1)*10;
    	}
    	cout<<ans;return 0;
    }
    
    • 0
      @ 2026-6-2 9:34:51

      先合成完所有竹子再进行加减,可以证明这样子对正确性没有影响。

      再因为这题的 nn 较小,考虑 dfs 。

      对于每一个子问题,我们需要他的层数 pp ,三个已和成竹子的长度 A,B,CA,B ,C ,还有已经用的魔法点 valval

      特别的,对于每一次更新答案,首先要判断它是不是有竹子组成的,最后算答案时应该把答案减去 3030 (因为一开始的时候不需要魔法点)。

      Code

      #include<iostream>
      #include<cmath>
      using namespace std;
      int l[10];
      int n,a,b,c,ans=1e9;
      void dfs(int p,int A,int B,int C,int val){
      	if(A!=0&&B!=0&&C!=0)
      		ans=min(ans,abs(A-a)+abs(B-b)+abs(C-c)+val-30);
      	if(p>n) 
          		return;
      	dfs(p+1,A+l[p],B,C,val+10);
      	dfs(p+1,A,B+l[p],C,val+10);
      	dfs(p+1,A,B,C+l[p],val+10);
      	dfs(p+1,A,B,C,val);
      	return;
      }
      int main(){
      	cin>>n>>a>>b>>c;
      	for(int i=1;i<=n;i++) 
      		cin>>l[i];
      	dfs(0,0,0,0,0);
      	cout<<ans;
      	return 0;
      }
      
      • 1

      信息

      ID
      11625
      时间
      2000ms
      内存
      1024MiB
      难度
      8
      标签
      递交数
      21
      已通过
      4
      上传者