网站建设需要会一些啥,电子商务网站开发过程,网络规划设计师科目分类,wordpress访问网站很慢这个dp我没做出来啊...其实不难..主要题意没理解好 fuck. 给你1-N这N个数 一共2^N-1个子集 每个子集的LCM值M的情况数有多少种 我也是醉了 这么个题目 给我套他那个题面 硬是没看懂 他在问什么 还是 英语太渣了 然后就是个 状态转移方程的考虑了 mapLL,LLdp[size]…这个dp我没做出来啊...其实不难..主要题意没理解好 fuck. 给你1-N这N个数 一共2^N-1个子集 每个子集的LCM值M的情况数有多少种 我也是醉了 这么个题目 给我套他那个题面 硬是没看懂 他在问什么 还是 英语太渣了 然后就是个 状态转移方程的考虑了 mapLL,LLdp[size] 表示 前size个数 构成的lcm值为 it-first的情况为 it-second种 dp[ i ] dp[ i-1 ] //不添加第 I 个元素 dp[ i ][ i ] //第I个元素自身构成的集合 for it - begin() - end() dp[ i][ it-fist ] it-second //第I个元素与前面的 I-1元素构成的集合组合出的情况 1 //给你1-N 这N个数 问有多少个子集 该集合的LCM M2 3 #include iostream4 #include map5 using namespace std;6 7 const int size 40;8 typedef long long LL;9 mapLL,LLdp[size5];//前 i 个数组合出的lcm值
10 mapLL,LL::iterator it;
11
12 LL gcd( LL x , LL y )
13 {
14 return x % y 0 ? y : gcd( y , x%y );
15 }
16
17 void init( int n )
18 {
19 dp[1][1] 1;
20 for( int i 1 ; in ; i )
21 {
22 dp[i] dp[i-1];
23 dp[i][i] ;
24 for( itdp[i-1].begin() ; it!dp[i-1].end(); it )
25 {
26 dp[i][ it-first*i/gcd(i,it-first) ] it-second;
27 }
28 }
29 }
30
31 int main()
32 {
33 cin.sync_with_stdio(false);
34 int n , t;
35 LL m , ans;
36 init( size );
37 cin t;
38 for( int k 1 ; kt ; k )
39 {
40 cin n m;
41 ans 0;
42 for( it dp[n].begin() ; it!dp[n].end() ; it )
43 {
44 if( it-firstm )
45 {
46 ans it-second;
47 }
48 }
49 cout Case # k : ans endl;
50 }
51 return 0;
52 } View Code 转载于:https://www.cnblogs.com/radical/p/4078438.html
