资讯

精准传达 • 有效沟通

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

网站建设 >

查看其它板块

SRM469-创新互联

250ptSRM469

    在一个10^9 * 10^9大的剧院里，有最多47个位子有人，然后有一对couple想找一对左右相邻的位子，问有多少种选择方式。

创新互联服务项目包括蟠龙网站建设、蟠龙网站制作、蟠龙网页制作以及蟠龙网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，蟠龙网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到蟠龙省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

思路：

   总共有 n * （m-1）种方案，然后扣掉有人位置占掉的方案即可。

   这里占掉位置我用一个set存储，正好可以去重。。

 1 #line 7 "TheMoviesLevelOneDivOne.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 TheMoviesLevelOneDivOne
42 {
43 public:
44 long long find(int n, int m, vector  row, vector  seat)
45         {
46   long long ans = n;
47                 ans =ans  * (m - 1); 
48   set< PII > S;
49   for (int i = 0; i < row.size(); ++i){
50  if (seat[i] > 1) S.insert(make_pair(row[i], seat[i]));
51  if (seat[i] + 1 <= m) S.insert(make_pair(row[i], seat[i] + 1));
52                 }
53                 ans -= S.size();
54   return ans;
55         }
56 
57 };
View Code

500pt

题意：一个人看电影，该人有一个scare值，并且没看1min电影scare减1。有很多部恐怖电影，每部电影长度不同(length[i])，且每部都有一个瞬间增加scare(s[i])值的时刻。如果scare值小于0，则这个人就会睡着，不能再看电影。请问他安排一个电影观看顺序，使得他能看尽可能多的电影。如果有多组观看顺序看到的电影数相同，则输出字典序最小的。(电影数量小等于20)

思路：

  状态压缩。。

 1 #line 7 "TheMoviesLevelTwoDivOne.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 int dp[1 << 20];
40 
41 class TheMoviesLevelTwoDivOne
42 {
43 public:
44         vector  find(vector  L, vector  scary)
45         {
46   int n = L.size();
47                 memset(dp, 0, sizeof(dp));
48   for (int i = 1; i < (1 << n); ++i){
49  int level = 74;
50  for (int j = 0; j < n; ++j)
51  if (!(i & (1 << j))) level += 47 - L[j];
52  for (int j = 0; j < n; ++j) if (i & (1 << j))
53  if (level >= scary[j] && level + 47 - L[j] >= 0)
54                             dp[i] = max(dp[i], dp[i ^ (1 << j)] + 1);
55                 }
56                 vector ans;
57   int x = 74, mask = (1 << n) - 1;
58   while (mask > 0){
59  for (int i = 0; i < n; ++i) if (mask & (1 << i))
60  if (dp[mask] == 0 ||
61                                (x >= scary[i] && x + 47 - L[i] >= 0 && dp[mask ^ (1 << i)] == dp[mask] - 1)){
62                                ans.PB(i);
63                                mask ^= (1 << i);
64                                x += 47 - L[i];
65   break;
66                             }
67                 }
68   return ans;
69         }
70 };
View Code
分享文章：SRM469-创新互联
新闻来源：http://cdkjz.cn/article/dcseie.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

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

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

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

在线咨询 提交需求
友情链接 交换友情链接
成都租用服务器成都SEO优化机柜租用四川盐亭做网站成都展柜制作香港云主机成都开元蓬安网站建设服务器托管恒翔机电

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

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

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