支付網(wǎng)站招聘費(fèi)分錄怎么做長(zhǎng)尾關(guān)鍵詞愛(ài)站網(wǎng)
文章目錄
- 思想
- 例題
- 1. 分成互質(zhì)組
- 題目鏈接
- 題目描述
- 【解法一】
- 【解法二】
- 2. 小貓爬山
- 題目鏈接
- 題目描述
- 輸入樣例:
- 輸出樣例:
- 【思路】
- 【W(wǎng)A代碼】
- 【AC代碼】
思想
- 本質(zhì)為兩種搜索順序:
- 枚舉當(dāng)前元素可以放入哪一組
- 枚舉每一組可以放入哪些元素
- 操作為兩種
- 放入當(dāng)前組
- 新開(kāi)一個(gè)組
例題
1. 分成互質(zhì)組
題目鏈接
https://www.acwing.com/problem/content/1120/
題目描述
【解法一】
枚舉每一組可以放哪些元素
#include <iostream>
using namespace std;
const int N = 11;
int g[N][N];
int a[N];
bool st[N];
int n;
int ans = N;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
bool check(int g[], int x, int k) {for(int i = 0; i < k; i ++)if(gcd(g[i], x) > 1) return false;return true;
}
void dfs(int gu, int gid, int start, int cnt) {if(gu >= ans) return ; //剪枝, 若當(dāng)前分組大于答案,那么不如之前的也沒(méi)必要枚舉了if(cnt == n) ans = min(ans, gu);bool flag = true; //從start開(kāi)始找,是否有元素不能入當(dāng)前組for(int i = start; i < n; i ++) {if(!st[i] && check(g[gu], a[i], gid)) {st[i] = true;g[gu][gid] = a[i];dfs(gu, gid + 1, i + 1, cnt + 1);//恢復(fù)現(xiàn)場(chǎng)st[i] = false;flag = false; }} //操作二:新開(kāi)數(shù)組if(flag) dfs(gu + 1, 0, 0, cnt);
}
int main() {cin >> n;for(int i = 0; i < n; i ++) cin >> a[i];//當(dāng)前在第幾組,第幾個(gè)數(shù),從哪個(gè)位置開(kāi)始選,已經(jīng)選好幾個(gè)數(shù) dfs(1, 0, 0, 0); cout << ans; return 0;
}
【解法二】
枚舉當(dāng)前元素可以放入哪個(gè)組
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;const int N = 10;
int a[N];
vector<int> g[N]; //互質(zhì)組
int n;
int ans = N;int gcd(int a, int b){return b?gcd(b, a%b) : a;
}bool check(int c,int x){for(int i=0;i<g[c].size();i++){if(gcd(g[c][i],x)>1) return false;}return true;
}void dfs(int u, int k){ //當(dāng)前為第u個(gè)數(shù), 已開(kāi)辟的組的個(gè)數(shù)if(u==n){ans=min(ans,k);return;}//每個(gè)元素的方法即 -> 放到當(dāng)前已經(jīng)存在的組中 或者 放到新開(kāi)的組中//操作一:放入已經(jīng)存在的組中for(int i=0; i < k; i ++){if(check(i, a[u])){g[i].push_back(a[u]);dfs(u + 1, k);g[i].pop_back();}}//可見(jiàn)這里的k代表著的是當(dāng)前開(kāi)辟數(shù)組的個(gè)數(shù)//操作二:新開(kāi)一個(gè)組g[k].push_back(a[u]);dfs(u+1, k + 1);g[k].pop_back();
}int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];dfs(0, 0);cout<<ans;return 0;
}
2. 小貓爬山
題目鏈接
https://www.acwing.com/problem/content/167/
題目描述
輸入樣例:
5 1996
1
2
1994
12
29
輸出樣例:
2
【思路】
第一步很容易會(huì)誤以為這是一道背包問(wèn)題,不過(guò)看了眼數(shù)據(jù)范圍,容量
太大,而n
的范圍很小,故為一道dfs
搜搜問(wèn)題
這里根據(jù)數(shù)據(jù)范圍我們必然需要優(yōu)化,分析可以?xún)?yōu)化的點(diǎn):
- ① 要求最小車(chē)輛,那么如果我們搜索某種決策時(shí)當(dāng)前的車(chē)輛數(shù)已經(jīng)大于
ans
了,那么必然不是最優(yōu)解,直接退出即可 - ② 對(duì)于
dfs
決策時(shí),要想使得決策的分支少點(diǎn),那么從根開(kāi)始越少的話,那么必然分支也會(huì)更少,想到從此處進(jìn)行優(yōu)化的話,那么若是優(yōu)先考慮重量大的,可以實(shí)現(xiàn),因?yàn)樵谝延械能?chē)輛中選擇可放入的重量大的可選車(chē)輛少
下面展示代碼:
【W(wǎng)A代碼】
枚舉每一組可以放入哪些元素
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, W;
int w[N];
int g[N][N];
bool st[N];
int ans = N;void dfs(int gu, int ct, int start, int cnt) {if(gu >= ans) return ;if(cnt == n) {ans = min(ans, gu);return;}bool flag = true; //判斷是否可以放進(jìn)去當(dāng)前組//操作一:加入當(dāng)前組 for(int i = start; i < n; i ++) {if(!st[i] && ct + w[i] <= W) {st[i] = true;dfs(gu, ct + w[i], start + 1, cnt + 1);//恢復(fù)現(xiàn)場(chǎng)st[i] = false; flag = false;}}//操作二:新開(kāi)組if(flag) dfs(gu + 1, 0, 0, cnt);}int main() {cin >> n >> W;for(int i = 0; i < n; i ++) cin >> w[i]; //為了使得決策少點(diǎn),優(yōu)化時(shí)間,選擇先放重量大的sort(w, w + n, greater<int>());//從第gu個(gè)組開(kāi)始,當(dāng)前在判斷第gid個(gè)數(shù),已經(jīng)匹配的數(shù)字, 從哪個(gè)數(shù)開(kāi)始 dfs(1, 0, 0, 0);cout << ans;return 0;
}
【AC代碼】
枚舉當(dāng)前元素可以放入哪些組
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, W;
int w[N];
int sum[N]; //第i輛車(chē)的重量
bool st[N];
int ans = N;void dfs(int u, int k) { //u代表當(dāng)前遍歷的數(shù),k代表當(dāng)前已有分組數(shù)量if(k >= ans) return;if(u == n) {// ans = min(ans, k); //因?yàn)橛猩喜綏l件制約,故不需要minans = k;return;} //操作一:放入某個(gè)已有的車(chē)輛for(int i = 0; i < k; i ++) {if(sum[i] + w[u] <= W) {sum[i] += w[u];dfs(u + 1, k);//恢復(fù)現(xiàn)場(chǎng)sum[i] -= w[u];}}//操作二: 放不下,新開(kāi)車(chē)輛sum[k] = w[u];dfs(u + 1, k + 1);sum[k] = 0;}int main() {cin >> n >> W;for(int i = 0; i < n; i ++) cin >> w[i]; //為了使得決策少點(diǎn),優(yōu)化時(shí)間,選擇先放重量大的sort(w, w + n, greater<int>());dfs(0, 0);cout << ans;return 0;
}