首页 > 其他 > 详细

LibreOJ #515

时间:2017-10-24 01:07:39      阅读:34      评论:0      收藏:0      [点我收藏+]

标签:count   http   情况   space   class   一个数   tps   表数   pre   

题目链接:https://loj.ac/problem/515

解题思路:

  DP部分不难想到:从 a 到 b 遍历,然后在已有的状态上加上遍历得到的数字的平方,难点在于记录状态。

  于是我学到了一个新的 C++ 类,bitset,开熏~

  S最大只能到 1000000,所以我们开一个比 1000000 稍大的 bitset 类,bitset 上面的各位代表数字 1~1000000,如果能得到一个数字,那么就在这个数字对应的位上置 1,否则置 0。那么加法运算就用移位符解决,各种情况的合并用 ‘|’ 来处理。

AC代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <bitset>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 bitset<1000005> dp[2];
 8 int main(){
 9     int pre=0,now=1;
10     dp[0][0]=1;
11     int n,a,b;
12     scanf("%d",&n);
13     while(n--){
14         dp[now]=0;
15         scanf("%d%d",&a,&b);
16         for(int i=a;i<=b;i++)
17             dp[now]|=(dp[pre]<<(i*i));
18         swap(now,pre);
19     }
20     printf("%d\n",dp[pre].count());
21     return 0;
22 }

 

LibreOJ #515

标签:count   http   情况   space   class   一个数   tps   表数   pre   

原文:http://www.cnblogs.com/Blogggggg/p/7719849.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号