中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁(yè) > news >正文

支付網(wǎng)站招聘費(fèi)分錄怎么做長(zhǎng)尾關(guān)鍵詞愛(ài)站網(wǎng)

支付網(wǎng)站招聘費(fèi)分錄怎么做,長(zhǎng)尾關(guān)鍵詞愛(ài)站網(wǎng),哈爾濱響應(yīng)式網(wǎng)站建設(shè)公司,tangxiaoding wordpress blog文章目錄 思想例題1. 分成互質(zhì)組題目鏈接題目描述【解法一】【解法二】 2. 小貓爬山題目鏈接題目描述輸入樣例:輸出樣例:【思路】【W(wǎng)A代碼】【AC代碼】 思想 本質(zhì)為兩種搜索順序: 枚舉當(dāng)前元素可以放入哪一組枚舉每一組可以放入哪些元素 操…

文章目錄

  • 思想
  • 例題
    • 1. 分成互質(zhì)組
      • 題目鏈接
      • 題目描述
      • 【解法一】
      • 【解法二】
    • 2. 小貓爬山
      • 題目鏈接
      • 題目描述
      • 輸入樣例:
      • 輸出樣例:
      • 【思路】
      • 【W(wǎng)A代碼】
      • 【AC代碼】

思想

  1. 本質(zhì)為兩種搜索順序
  • 枚舉當(dāng)前元素可以放入哪一組
  • 枚舉每一組可以放入哪些元素
  1. 操作為兩種
  • 放入當(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;
}
http://www.risenshineclean.com/news/48976.html

相關(guān)文章:

  • 網(wǎng)站建設(shè)和注冊(cè)北京seo包年
  • 一站式網(wǎng)站建設(shè)服務(wù)今日熱搜第一名
  • 開(kāi)封做網(wǎng)站公司漢獅外貿(mào)網(wǎng)站seo優(yōu)化
  • 建設(shè)網(wǎng)站證書(shū)西安百度seo
  • 濟(jì)源網(wǎng)站建設(shè)濟(jì)源百度地圖在線查詢(xún)
  • 國(guó)外商業(yè)網(wǎng)站設(shè)計(jì)廣東深圳疫情最新消息今天
  • 互聯(lián)網(wǎng)行業(yè)最有前景的十大職業(yè)手機(jī)網(wǎng)站排名優(yōu)化
  • wordpress自動(dòng)廣告位二級(jí)域名和一級(jí)域名優(yōu)化難度
  • 撰寫(xiě)網(wǎng)站的建設(shè)方案北京seo服務(wù)商
  • 賢邦網(wǎng)站建設(shè)app開(kāi)發(fā)公司網(wǎng)絡(luò)營(yíng)銷(xiāo)推廣
  • 做網(wǎng)站創(chuàng)業(yè)app排名優(yōu)化
  • 做網(wǎng)站建設(shè)的公司有哪些內(nèi)容房地產(chǎn)估價(jià)師考試
  • 電商網(wǎng)站功能介紹百度seo排名優(yōu)化公司推薦
  • 網(wǎng)站建設(shè)沒(méi)業(yè)務(wù)互聯(lián)網(wǎng)產(chǎn)品推廣
  • 購(gòu)物網(wǎng)站建設(shè)網(wǎng)站seo實(shí)戰(zhàn)密碼第三版pdf下載
  • 四川網(wǎng)站建設(shè)培訓(xùn)班百度助手下載安裝
  • 制作網(wǎng)站模板的發(fā)展空間網(wǎng)站搜索引擎優(yōu)化工具
  • 動(dòng)態(tài)網(wǎng)站開(kāi)發(fā)采用的關(guān)鍵技術(shù)百度入口網(wǎng)頁(yè)版
  • 西安做百度網(wǎng)站的上海職業(yè)技能培訓(xùn)機(jī)構(gòu)一覽表
  • 南昌網(wǎng)站建設(shè)優(yōu)化推廣費(fèi)用百度指數(shù)分析報(bào)告案例
  • 寧波做網(wǎng)站哪家公司好網(wǎng)站設(shè)計(jì)公司蘇州
  • 武漢市二手房交易合同備案在那個(gè)網(wǎng)站上做呀如何讓網(wǎng)站快速收錄
  • 網(wǎng)站制作 牛商網(wǎng)外鏈查詢(xún)工具
  • 手把手教做網(wǎng)站網(wǎng)站優(yōu)化策略
  • 做京東網(wǎng)站需要哪些手續(xù)費(fèi)企業(yè)推廣app
  • l網(wǎng)站建設(shè)線上營(yíng)銷(xiāo)手段
  • 國(guó)外效果超炫網(wǎng)站北京seo優(yōu)化診斷
  • 河北網(wǎng)站建設(shè)排名優(yōu)化哪家專(zhuān)業(yè)
  • 網(wǎng)站怎樣免費(fèi)推廣網(wǎng)絡(luò)營(yíng)銷(xiāo)專(zhuān)業(yè)課程
  • 杭州裝飾網(wǎng)站建設(shè)互聯(lián)網(wǎng)營(yíng)銷(xiāo)的方法