首页 > 代码库 > hdu--4028--dp

hdu--4028--dp

2024-07-31 14:20:55   213人阅读

这个dp我没做出来啊...其实不难..主要题意没理解好 fuck.

给你1-N这N个数  一共2^N-1个子集 每个子集的LCM值>=M的情况数有多少种

我也是醉了 这么个题目 给我套他那个题面 硬是没看懂 他在问什么 还是 英语太渣了

然后就是个 状态转移方程的考虑了

map<LL,LL>dp[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 >= M 2  3 #include <iostream> 4 #include <map> 5 using namespace std; 6  7 const int size = 40; 8 typedef long long LL; 9 map<LL,LL>dp[size+5];//前 i 个数组合出的lcm值10 map<LL,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 ; i<=n ; i++ )21     {22         dp[i] = dp[i-1];23         dp[i][i] ++;24         for( it=dp[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 ; k<=t ; k++ )39     {40         cin >> n >> m;41         ans = 0;42         for( it = dp[n].begin() ; it!=dp[n].end() ; it++ )43         {44             if( it->first>=m )45             {46                 ans += it->second;47             }48         }49         cout << "Case #" << k << ": " << ans << endl;50     }51     return 0;52 }
View Code

 

hdu--4028--dp


联系
我们