2 条题解
-
0
能写出这种代码,我的思维真不是正常人能达到的高度了
#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
先合成完所有竹子再进行加减,可以证明这样子对正确性没有影响。
再因为这题的 较小,考虑 dfs 。
对于每一个子问题,我们需要他的层数 ,三个已和成竹子的长度 ,还有已经用的魔法点 。
特别的,对于每一次更新答案,首先要判断它是不是有竹子组成的,最后算答案时应该把答案减去 (因为一开始的时候不需要魔法点)。
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
- 上传者