SRM476-創(chuàng)新互聯(lián)

250ptSRM476

題意：飼養(yǎng)N<=50只Badgers，每只食量是X[i]，當(dāng)沒看到別的一只Badgers吃東西時，它的食量就會增加Y[i]，現(xiàn)在一共用P的糧食，問最多能養(yǎng)的起多少只獾。

創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站設(shè)計(jì)制作、成都做網(wǎng)站、鐘山網(wǎng)絡(luò)推廣、小程序定制開發(fā)、鐘山網(wǎng)絡(luò)營銷、鐘山企業(yè)策劃、鐘山品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供鐘山建站搭建服務(wù)，24小時服務(wù)熱線：13518219792，官方網(wǎng)址：muchs.cn

思路：枚舉一下養(yǎng)多少只。那么接下來貪心即可。

code：

 1 #line 7 "Badgers.cpp"
 2 #include <cstdlib>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <string>
10 #include <iostream>
11 #include <sstream>
12 #include <map>
13 #include <set>
14 #include <queue>
15 #include <stack>
16 #include <fstream>
17 #include <numeric>
18 #include <iomanip>
19 #include <bitset>
20 #include <list>
21 #include <stdexcept>
22 #include <functional>
23 #include <utility>
24 #include <ctime>
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 
34 typedef vector<int> VI;
35 typedef vector<string> VS;
36 typedef vector<double> VD;
37 typedef long long LL;
38 typedef pair<int,int> PII;
39 
40 
41 class Badgers
42 {
43 public:
44 int feedMost(vector <int> a, vector <int> b, int totalFood)
45         {
46   int n = a.size();
47                    vector<int> c;
48   for (int i = n; i > 0; --i){
49                          c.clear();
50   for (int j = 0; j < n; ++j)
51                              c.PB(a[j] + (i - 1) * b[j]);
52                          sort(c.begin(), c.end());
53   int sum = 0;
54   for (int j = 0; j < i; ++j)
55                              sum += c[j];
56   if (sum <= totalFood) return i;
57                    }
58   return 0;
59         }
60 };
View Code

500pt

題意：某社交網(wǎng)站上有N<=36個人，每個人的頁面只會隨機(jī)顯示K<=36個好友，如果好友數(shù)不足K則全部顯示?，F(xiàn)在0號人先從自己的頁面開始，每次訪問一個還沒訪問過的好友，然后在訪問該好友的好友中自己還沒訪問過的自己的好友。也就是說他只會訪問自己的好友，且每個好友只會訪問一次。在知道所有好友關(guān)系的情況下，問在最優(yōu)策略下0號人有多少的概率能訪問到他的所有好友。

思路：注意到字符串長度最多36，并且中間有空格，那么每個人最多也就15個好友，并且每次只會訪問他還沒訪問的好友。

    所以動態(tài)規(guī)劃+枚舉即可

    dp[i][mask]表示訪問0的第i個好友，并且訪問好友的情況為mask情況下的最優(yōu)解。

    統(tǒng)計(jì)時相對麻煩點(diǎn)。要按概率第一高，第二的順序枚舉。。具體看代碼吧

code:

  1 #line 7 "FriendTour.cpp"
  2 #include <cstdlib>
  3 #include <cctype>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <vector>
  9 #include <string>
 10 #include <iostream>
 11 #include <sstream>
 12 #include <map>
 13 #include <set>
 14 #include <queue>
 15 #include <stack>
 16 #include <fstream>
 17 #include <numeric>
 18 #include <iomanip>
 19 #include <bitset>
 20 #include <list>
 21 #include <stdexcept>
 22 #include <functional>
 23 #include <utility>
 24 #include <ctime>
 25 using namespace std;
 26 #define M0(a) memset(a, 0, sizeof(a))
 27 #define PB push_back
 28 #define MP make_pair
 29 
 30 #define REP(i,n) for(i=0;i<(n);++i)
 31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
 32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
 33 #define two(i) (1 << i)
 34 typedef vector<int> VI;
 35 typedef vector<string> VS;
 36 typedef vector<double> VD;
 37 typedef long long LL;
 38 typedef pair<int,int> PII;
 39 vector<int> g[38];
 40 double dp[1 << 18][18];
 41 double c[40][40];
 42 bool vis[1 << 18][18];
 43 int P[38];
 44 class FriendTour
 45 {
 46 public:
 47 int n, m, k;
 48 void make_friend(int k, string S){
 49                g[k].clear();
 50   //     if (k == 0) g[k].push_back(k); 51  int len = S.size();
 52  int tmp = 0;
 53  for (int i = 0; i < len; ++i)
 54   if (S[i] == ' '){
 55                       g[k].push_back(--tmp);
 56                       tmp = 0;
 57                    }else tmp = tmp * 10 + S[i] - 48;
 58  if (tmp) g[k].push_back(--tmp);
 59 
 60         }
 61 void dfs(int S, int L){
 62   if (vis[S][L]) return;
 63              vis[S][L] = true;
 64              dp[S][L] = 0;
 65   if (S == two(n+1)-1){ dp[S][L] = 1.0; return; }
 66   int x = 0;
 67   if (L > 0) x = g[0][L-1];
 68              vector<double> v;
 69   for (int i = 0; i < g[x].size(); ++i){
 70   if (P[g[x][i]] == 0 || (S & two(P[g[x][i]]))) continue;
 71                    dfs(S | two(P[g[x][i]]), P[g[x][i]]);
 72                    v.push_back(dp[S | two(P[g[x][i]])][P[g[x][i]]]);
 73              }
 74              sort(v.begin(), v.end(), greater<double>());
 75   int total = g[x].size(), d = min(k, total);
 76 //  double c1; 77   for (int i = 0; i < v.size(); ++i){
 78  //       c1 = v[i]; 79                    dp[S][L] += v[i] * c[total-i-1][d-1];
 80              }
 81              dp[S][L] /= c[total][d];
 82         }
 83 double tourProbability(vector <string> friends, int K)
 84         {
 85                m = friends.size();
 86  for (int i = 0; i < m; ++i) make_friend(i, friends[i]);
 87  for (int i = 0; i <= 36; ++i){
 88                     c[i][0] = 1.0;
 89 for (int j = 1; j <= i; ++j)
 90                          c[i][j] = c[i-1][j] + c[i-1][j-1];
 91                }
 92   //  M0(dp); 93                M0(vis);
 94                n = g[0].size();
 95 // cout << n << endl; 96                M0(P);
 97  for (int i = 0; i < n; ++i) P[g[0][i]] = i + 1;// cout << g[0][i] << endl; 98                k = K;
 99                dfs(1, 0);
100  return dp[1][0];
101         }
102 };
View Code

分享標(biāo)題：SRM476-創(chuàng)新互聯(lián)
網(wǎng)頁路徑：http://muchs.cn/article32/deijpc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、云服務(wù)器、ChatGPT、商城網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

h5響應(yīng)式網(wǎng)站建設(shè)