从两侧同时展开,那测数据少就从哪侧展,两者展开结果出现一样的,返回答案
127. 单词接龙 - 力扣（LeetCode）
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> dict(wordList.begin(),wordList.end());if(dict.find(endWord)==dict.end())return 0;unordered_set<string> smalllevel,biglevel,nextlevel;smalllevel.insert(beginWord);biglevel.insert(endWord);for(int len=2;!smalllevel.empty();len++){for(string s:smalllevel){string w=s;for(int i=0;i<w.length();i++){char old=w[i];for(char ch='a';ch<='z';ch++){if(ch!=old){w[i]=ch;if(biglevel.find(w)!=biglevel.end())return len;if(dict.find(w)!=dict.end()){//塞入nextlevelnextlevel.insert(w);dict.erase(w);}}}w[i]=old;}}if(nextlevel.size()<=biglevel.size()){smalllevel=nextlevel;nextlevel.clear();}else{smalllevel=biglevel;biglevel=nextlevel;nextlevel.clear();}}return 0;}
};第二种用法:分成左右两半时暴力展开,把所有结果再整合再一起
牛牛的背包问题
由于这道题目的数据范围过大,达到10的9次方,所以动态规划方法无法通过
P4799 [CEOI 2015] 世界冰球锦标赛 (Day2) - 洛谷
#include<bits/stdc++.h>
using namespace std;
const int maxn=40;
long long arr[maxn],w;
vector<long long>lsum,rsum;
int n;
void dfs(int i,int end,long long path,vector<long long> &ans)
{if(path>w)return;if(i==end+1)ans.push_back(path);else{dfs(i+1,end,path+arr[i],ans);dfs(i+1,end,path,ans);}
}
int main()
{cin>>n>>w;for(int i=1;i<=n;i++)cin>>arr[i];dfs(1,n/2,0,lsum);dfs(n/2+1,n,0,rsum);sort(lsum.begin(),lsum.end());sort(rsum.begin(),rsum.end());long long ans=0;for(int i=lsum.size()-1,j=0;i>=0;i--){while(j<rsum.size()&&lsum[i]+rsum[j]<=w)j++;ans+=j;}cout<<ans;
}最接近目标的子序列和
1755. 最接近目标值的子序列和 - 力扣（LeetCode）
class Solution {
public:vector<int> lsum,rsum;int minAbsDifference(vector<int>& nums, int goal) {int n=nums.size();f(0,n/2,nums,lsum,0);f(n/2,n,nums,rsum,0);sort(lsum.begin(),lsum.end());sort(rsum.begin(),rsum.end());int ans=INT_MAX;for(int l=0,r=rsum.size()-1;l<lsum.size();l++){while(r>0&&abs(lsum[l]+rsum[r]-goal)>=abs(lsum[l]+rsum[r-1]-goal))r--;ans=min(ans,abs(lsum[l]+rsum[r]-goal));}return ans;}void f(int i,int end,vector<int> &nums,vector<int>& ans,long long path){if(i==end)ans.push_back(path);else{//这里选择了按组展开int j=i+1;for(;j<end&&nums[j]==nums[i];j++);for(int k=0;k<=j-i;k++)f(j,end,nums,ans,path+k*nums[i]);}}
};
