资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

SRM476-创新互联

250ptSRM476

题意：饲养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://cdkjz.cn/article/deijpc.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
成都光华机房服务器托管重庆托管服务器成都IDC机房托管简阳机房托管成都办公窗帘软文营销成都帛金建站成都网站设计公司响应式网站成都气球装饰

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图