SRM476-创新互联

250pt

题意：饲养N<=50只Badgers，每只食量是X[i]，当没看到别的一只Badgers吃东西时，它的食量就会增加Y[i]，现在一共用P的粮食，问最多能养的起多少只獾。

创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于网站设计制作、成都做网站、钟山网络推广、小程序定制开发、钟山网络营销、钟山企业策划、钟山品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；创新互联建站为所有大学生创业者提供钟山建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

思路：枚举一下养多少只。那么接下来贪心即可。

code：

 1 #line 7 "Badgers.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
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 VI;
35 typedef vector VS;
36 typedef vector VD;
37 typedef long long LL;
38 typedef pair PII;
39 
40 
41 class Badgers
42 {
43 public:
44 int feedMost(vector  a, vector  b, int totalFood)
45         {
46   int n = a.size();
47                    vector 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

题意：某社交网站上有N<=36个人，每个人的页面只会随机显示K<=36个好友，如果好友数不足K则全部显示。现在0号人先从自己的页面开始，每次访问一个还没访问过的好友，然后在访问该好友的好友中自己还没访问过的自己的好友。也就是说他只会访问自己的好友，且每个好友只会访问一次。在知道所有好友关系的情况下，问在最优策略下0号人有多少的概率能访问到他的所有好友。

思路：注意到字符串长度最多36，并且中间有空格，那么每个人最多也就15个好友，并且每次只会访问他还没访问的好友。

所以动态规划+枚举即可

dp[i][mask]表示访问0的第i个好友，并且访问好友的情况为mask情况下的最优解。

统计时相对麻烦点。要按概率第一高，第二的顺序枚举。。具体看代码吧

code:

  1 #line 7 "FriendTour.cpp"
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include 
 10 #include 
 11 #include 
 12 #include 
 13 #include 
 14 #include 
 15 #include 
 16 #include 
 17 #include 
 18 #include 
 19 #include 
 20 #include 
 21 #include 
 22 #include 
 23 #include 
 24 #include 
 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 VI;
 35 typedef vector VS;
 36 typedef vector VD;
 37 typedef long long LL;
 38 typedef pair PII;
 39 vector 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 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());
 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  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
网页题目：SRM476-创新互联
文章分享：http://azwzsj.com/article/deijpc.html

SRM476-创新互联

其他资讯