問(wèn)題 A: algorithm-迷宮游戲
題目描述
你來(lái)到一個(gè)迷宮前。該迷宮由若干個(gè)房間組成，每個(gè)房間都有一個(gè)得分，第一次進(jìn)入這個(gè)房間，你就可以得到這個(gè)分?jǐn)?shù)。還有若干雙向道路連結(jié)這些房間，你沿著這些道路從一個(gè)房間走到另外一個(gè)房間需要一些時(shí)間。游戲規(guī)定了你的起點(diǎn)和終點(diǎn)房間，你首要目標(biāo)是從起點(diǎn)盡快到達(dá)終點(diǎn)，在滿足首要目標(biāo)的前提下，使得你的得分總和盡可能大。現(xiàn)在問(wèn)題來(lái)了，給定房間、道路、分?jǐn)?shù)、起點(diǎn)和終點(diǎn)等全部信息，你能計(jì)算在盡快離開(kāi)迷宮的前提下，你的最大得分是多少么？
輸入
第一行4個(gè)整數(shù)n (<=500), m, start, end。n表示房間的個(gè)數(shù)，房間編號(hào)從0到(n - 1)，m表示道路數(shù),任意兩個(gè)房間之間最多只有一條道路，start和end表示起點(diǎn)和終點(diǎn)房間的編號(hào)。
第二行包含n個(gè)空格分隔的正整數(shù)(不超過(guò)600)，表示進(jìn)入每個(gè)房間你的得分。
再接下來(lái)m行，每行3個(gè)空格分隔的整數(shù)x, y, z (0<z<=200)表示道路,表示從房間x到房間y(雙向)的道路,注意，最多只有一條道路連結(jié)兩個(gè)房間,你需要的時(shí)間為z。
輸入保證從start到end至少有一條路徑。
輸出
占一行，分別最短時(shí)間和相應(yīng)的最大得分，中間用空格隔開(kāi)。
樣例輸入 Copy
3 2 0 2
1 2 3
0 1 10
1 2 11
樣例輸出 Copy
21 6

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<vector> #include<queue> using namespace std;#define Int __int64 #define INF 0x3f3f3f3fconst int MAXN = 555; int n, m, s, e;int maze[MAXN][MAXN]; int dis[MAXN]; bool vis[MAXN]; int score[MAXN]; int ans[MAXN];void init() {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) maze[i][j] = 0;else maze[i][j] = INF;}}memset(dis, 0, sizeof(dis));memset(vis, false, sizeof(vis));memset(ans, false, sizeof(ans)); }void Dijkstra() {for (int i = 0; i < n; i++) {scanf("%d", &score[i]);}int u, v, w;for (int i = 0; i < m; i++) {scanf("%d %d %d", &u, &v, &w);if (w < maze[u][v]) {maze[u][v] = w;maze[v][u] = w;}}for (int i = 0; i < n; i++) {dis[i] = maze[s][i];if (i != s) ans[i] = score[s] + score[i];//初始化的時(shí)候也要判斷等于的情況else ans[i] = score[i];}for (int i = 0; i < n; i++) {int pos, Min = INF;for (int a = 0; a < n; a++) {if (vis[a]) continue;if (dis[a] < Min) {Min = dis[a];pos = a;}}vis[pos] = true;for (int a = 0; a < n; a++) {if (maze[pos][a] < INF) {if (dis[a] > dis[pos] + maze[pos][a]) {dis[a] = dis[pos] + maze[pos][a];ans[a] = ans[pos] + score[a];} else if ((dis[a] == dis[pos] + maze[pos][a]) && (ans[a] < ans[pos] + score[a]) && pos != a) {/*就是這里要判斷等于的時(shí)候是不行的*/ans[a] = ans[pos] + score[a];} else {continue;}}}} } int main() {//freopen("input.txt", "r", stdin);while (scanf("%d %d %d %d", &n, &m, &s, &e) != EOF) {init();Dijkstra();printf("%d %d\n", dis[e], ans[e]);}return 0; }

問(wèn)題 B: algorithm-Homework
[命題人 : 080063]
時(shí)間限制 : 1.000 sec 內(nèi)存限制 : 128 MB

題目描述
臨近開(kāi)學(xué)了，大家都忙著收拾行李準(zhǔn) 備返校，但 I_Love_C 卻不為此擔(dān)心! 因?yàn)樗男乃既谑罴僮鳂I(yè)上：目前為止還未開(kāi)動(dòng)。
暑假作業(yè)是很多張?jiān)嚲?#xff0c;我們這些從試卷里爬出來(lái)的人都知道，卷子上的題目有選擇題、填空題、簡(jiǎn)答題、證明題等。而做選擇題的好處就在于工作量很少，但又因?yàn)檫x擇題題目都普遍很長(zhǎng)。如果有 5 張?jiān)嚲?#xff0c;其中 4 張是選擇題，最后一張是填空題，很明顯做最后一張所花的時(shí)間要比前 4 張長(zhǎng)很多。但如果你只做了選擇題，雖然工作量很少，但表面上看起來(lái)也已經(jīng)做了4/5的作業(yè)了。
I_Love_C決定就用這樣的方法來(lái)蒙混過(guò)關(guān)，他統(tǒng)計(jì)出了做完每一張?jiān)嚲硭璧臅r(shí)間以及它做完后能得到的價(jià)值（按上面的原理，選擇題越多價(jià)值當(dāng)然就越高咯）。
現(xiàn)在就請(qǐng)你幫他安排一下，用他僅剩的一點(diǎn)時(shí)間來(lái)做最有價(jià)值的作業(yè)。
輸入
測(cè)試數(shù)據(jù)包括多組。每組測(cè)試數(shù)據(jù)以兩個(gè)整數(shù) M,N(1<M<20,1<N<10000) 開(kāi)頭，分別表示試卷的數(shù)目和 I_Love_C 剩下的時(shí)間。接下來(lái)有 M 行，每行包括兩個(gè)整數(shù) T,V(1<T<N,1<V<10000)分別表示做完這張?jiān)嚲硭璧臅r(shí)間以及做完后能得到的價(jià)值，輸入以 0 0 結(jié)束。
輸出
對(duì)應(yīng)每組測(cè)試數(shù)據(jù)輸出 I_Love_C 能獲得的最大價(jià)值。保留小數(shù)點(diǎn) 2 位
提示：float 的精度可能不夠，你應(yīng)該使用 double 類(lèi)型。
樣例輸入 Copy
4 20
4 10
5 22
10 3
1 2
0 0
樣例輸出 Copy
37.00

#include <iostream> #include <algorithm> #include <vector> #include <iomanip> using namespace std;struct Paper {int time;int value;double perValue;bool operator<(const Paper & h) const{return (h.perValue < perValue);} };int main() {int M, N;while (cin >> M >> N && (M || N)){vector<Paper> list(M);for (int i = 0; i < M; ++i){cin >> list[i].time >> list[i].value;list[i].perValue = list[i].value / double(list[i].time);}sort(list.begin(), list.end());double sum = 0;for (int i = 0; i < M; ++i){if (N >= list[i].time){sum += list[i].value;N -= list[i].time;}else{sum += list[i].perValue * N;break;}}cout << setiosflags(ios::fixed) << setprecision(2) << sum << endl;}return 0; }

問(wèn)題 C: algorithm-哈夫曼編碼
[命題人 : 080063]
時(shí)間限制 : 1.000 sec 內(nèi)存限制 : 128 MB

題目描述
給定一只含有小寫(xiě)字母的字符串；輸出其哈夫曼編碼的長(zhǎng)度
輸入
第一行一個(gè)整數(shù)T，代表樣例的個(gè)數(shù)，接下來(lái)T行，每行一個(gè)字符串，0<T<=2000,字符串長(zhǎng)度0<L<=1500.
輸出
對(duì)于每個(gè)字符串，輸出其哈夫曼編碼長(zhǎng)度
樣例輸入 Copy
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq
樣例輸出 Copy
10
51
115

#include<iostream> #include<queue> #include<string.h> using namespace std; int main() {int t;cin>>t;while(t--){char s[2000];cin>>s;int fre[26]={0};int len=strlen(s);for(int i=0;i<len;i++){fre[s[i]-'a']++;}priority_queue<int,vector<int>,greater<int> >q;for(int i=0;i<26;i++){if(fre[i]>0){q.push(fre[i]);}}int sum=0;while(q.size()>=2){int a=q.top();q.pop();int b=q.top();q.pop();sum+=(a+b);q.push(a+b);}cout<<sum<<endl;}return 0; }

問(wèn)題 D: algorithm-汽車(chē)費(fèi)用
[命題人 : 080063]
時(shí)間限制 : 1.000 sec 內(nèi)存限制 : 128 MB

題目描述
一個(gè)特別的單行街道在每公里處有一個(gè)汽車(chē)站。顧客根據(jù)他們乘坐汽車(chē)的公里使來(lái)付費(fèi)。例如下表就是一個(gè)費(fèi)用的單子。沒(méi)有一輛車(chē)子行駛超過(guò)10公里，一個(gè)顧客打算行駛n公里(1<=n<100)，它可以通過(guò)無(wú)限次的換車(chē)來(lái)完成旅程。最后要求費(fèi)用最少。
輸入
第一行十個(gè)整數(shù)分別表示行走1到10公里的費(fèi)用(<=500)。注意這些數(shù)并無(wú)實(shí)際的經(jīng)濟(jì)意義，即行駛10公里費(fèi)用可能比行駛一公里少。第二行一個(gè)整數(shù)n表示，旅客的總路程數(shù)。
輸出
僅一個(gè)整數(shù)表示最少費(fèi)用。

樣例輸入 Copy
12 21 31 40 49 58 69 79 90 101
15
樣例輸出 Copy
147

#include<iostream> #include<vector> using namespace std; int main(){vector<int> res=vector<int>(11,0);for(int i=1;i<=10;i++){cin>>res[i];}int m;cin>>m;vector<int> ans=vector<int>(m+1,10000);ans[0]=0;for(int i=1;i<=10;i++){for(int j=i;j<=m;j++){ans[j]=min(ans[j],ans[j-i]+res[i]);}}cout<<ans[m]; }

問(wèn)題 E: algorithm-八皇后問(wèn)題
[命題人 : 080063]
時(shí)間限制 : 1.000 sec 內(nèi)存限制 : 128 MB

題目描述
努比亞和蘇丹沒(méi)有子女，所以他要從一些有集成資格的繼承者中挑選一個(gè)出來(lái)繼承王位。他希望這個(gè)繼承者足夠聰明，所以他準(zhǔn)備了一個(gè)西洋棋盤(pán)，上面的每個(gè)格子中均有一個(gè) 1-99 的數(shù)字。他又準(zhǔn)備了 8 個(gè)皇后棋子。
8 皇后的規(guī)則就是不能有任何棋子同行或者同列或者同斜線，在滿足這個(gè)規(guī)則的同時(shí)，王位繼承者還需要讓 8 個(gè)皇后所在的位置的數(shù)字的和是最大的。
輸入
輸入一個(gè)數(shù)字 k(k≤20)，代表棋盤(pán)的數(shù)量。
接下來(lái)有 k 個(gè)棋盤(pán)，每個(gè)棋盤(pán)有 64 個(gè)數(shù)字，分成 8 行 8 列輸入，具體可見(jiàn)樣例，每一個(gè)數(shù)字均小于 100。
輸出
每一個(gè)棋盤(pán)對(duì)應(yīng)輸出最大的數(shù)值， 一共輸出 k行
樣例輸入 Copy
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
樣例輸出 Copy
260

#include<iostream> #include<vector> using namespace std; int result; void dfs(vector<vector<int> >&m,vector<bool>res,vector<pair<int,int> >check,int start,int n,int sum){if(n==8){result=max(result,sum);return;}bool flag=1;for(int i=0;i<8;i++){if(!res[i]){flag=1;for(int j=0;j<check.size();j++){if(start+i==check[j].first+check[j].second||start-i==check[j].first-check[j].second){flag=0;break;}}if(flag) {res[i] = 1;check.push_back(make_pair(start , i));dfs(m, res, check, start + 1, n + 1, sum + m[start][i]);check.pop_back();res[i] = 0;}}} } int main(){vector<bool> res=vector<bool>(8,0);vector<pair<int,int> >check;int len;cin>>len;while(len--) {result=0;vector<vector<int> > sex = vector<vector<int> >(8, vector<int>(8, 0));for (int i = 0; i < 8; i++) {for (int j = 0; j < 8; j++) {cin >> sex[i][j];}}dfs(sex,res,check,0,0,0);cout<<result<<endl;}return 0; }

問(wèn)題 F: algorithm-法師康的工人
[命題人 : 080063]
時(shí)間限制 : 1.000 sec 內(nèi)存限制 : 128 MB

題目描述
三個(gè)法師康的工人每天早上6點(diǎn)到工廠開(kāi)始到三條產(chǎn)品生產(chǎn)線上組裝桔子手機(jī)。第一個(gè)工人在200時(shí)刻開(kāi)始（從6點(diǎn)開(kāi)始計(jì)時(shí)，以秒作為單位）在生產(chǎn)線上開(kāi)始生產(chǎn)，一直到1000時(shí)刻。第二個(gè)工人，在700時(shí)刻開(kāi)始，在1100時(shí)刻結(jié)束。第三個(gè)工人從1500時(shí)刻工作到2100時(shí)刻。期間最長(zhǎng)至少有一個(gè)工人在生產(chǎn)線上工作的連續(xù)時(shí)間為900秒（從200時(shí)刻到1100時(shí)刻），而最長(zhǎng)的無(wú)人生產(chǎn)的連續(xù)時(shí)間（從生產(chǎn)開(kāi)始到生產(chǎn)結(jié)束）為400時(shí)刻（1100時(shí)刻到1500時(shí)刻）。
你的任務(wù)是用一個(gè)程序衡量N個(gè)工人在N條產(chǎn)品線上的工作時(shí)間列表（1≤N≤5000，以秒為單位）。
·最長(zhǎng)的至少有一個(gè)工人在工作的時(shí)間段
·最長(zhǎng)的無(wú)人工作的時(shí)間段（從有人工作開(kāi)始計(jì)）
輸入
輸入第1行為一個(gè)整數(shù)N，第2-N+1行每行包括兩個(gè)均小于1000000的非負(fù)整數(shù)數(shù)據(jù)，表示其中一個(gè)工人的生產(chǎn)開(kāi)始時(shí)間與結(jié)束時(shí)間。
輸出
輸出為一行，用空格分隔開(kāi)兩個(gè)我們所求的數(shù)。
樣例輸入 Copy
3
200 1000
700 1100
1500 2100
樣例輸出 Copy
900 400

#include<iostream> #include<algorithm> #include<vector> using namespace std; bool compare(pair<int,int> a,pair<int,int> b){if(a.first==b.first)return a.second<b.second;return a.first<b.first; } int main(){int a;cin>>a;vector<pair<int,int> > res=vector<pair<int,int> >(a);for(int i=0;i<a;i++){cin>>res[i].first>>res[i].second;}sort(res.begin(),res.end(),compare);int freetime=0;int busytime=res[0].second-res[0].first;for(int i=1;i<a;i++){if(res[i].first<=res[i-1].second){res[i].first=res[i-1].first;res[i].second=max(res[i-1].second,res[i].second);}else{freetime=max(freetime,res[i].first-res[i-1].second);}busytime=max(busytime,res[i].second-res[i].first);}cout<<busytime<<" "<<freetime<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析-实验2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。