1 solutions
-
1
普普通通的搜索,重点是sort的cmp该怎么写
#include<bits/stdc++.h> using namespace std; typedef long int li; const int N=1e6+7; int n,sum,T; li a[N]; vector<int>v; vector<vector<int> >ans; int cmp(vector<int> &a,vector<int> &b){ int l1=a.size(),l2=b.size(); int len=min(l1,l2); for(int i=0;i<len;i++){ if(a[i]==b[i])continue; return a[i]<b[i]; } return l1<l2; } void dfs(int s,int su){ if(su==T){ ans.push_back(v); sum++; } for(int i=s-1;i>=1;i--){ v.push_back(i); dfs(i,su+a[i]); v.pop_back(); } } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cin>>T; for(int i=1;i<=n;i++){ v.push_back(i); dfs(i,a[i]); v.pop_back(); } sort(ans.begin(),ans.end(),cmp); for(vector<int> t:ans){ for(int i=t.size()-1;i>=0;i--) cout<<a[t[i]]<<" "; cout<<endl; } cout<<sum<<endl; return 0; }
- 1
Information
- ID
- 1760
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 10
- Tags
- # Submissions
- 3
- Accepted
- 2
- Uploaded By