這個(gè)dp我沒做出來啊...其實(shí)不難..主要題意沒理解好 fuck.

給你1-N這N個(gè)數(shù)? 一共2^N-1個(gè)子集 每個(gè)子集的LCM值>=M的情況數(shù)有多少種

我也是醉了 這么個(gè)題目 給我套他那個(gè)題面 硬是沒看懂 他在問什么 還是 英語太渣了

然后就是個(gè) 狀態(tài)轉(zhuǎn)移方程的考慮了

map<LL,LL>dp[size] 表示? 前size個(gè)數(shù) 構(gòu)成的lcm值為 it->first的情況為 it->second種

dp[ i ] = dp[ i-1 ]? //不添加第 I 個(gè)元素

dp[ i ][ i ] ++//第I個(gè)元素自身構(gòu)成的集合

for it - >?? begin() -? end()

dp[ i][ it->fist ] += it->second //第I個(gè)元素與前面的 I-1元素構(gòu)成的集合組合出的情況

?

1 //給你1-N 這N個(gè)數(shù) 問有多少個(gè)子集 該集合的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 個(gè)數(shù)組合出的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

?

轉(zhuǎn)載于:https://www.cnblogs.com/radical/p/4078438.html

總結(jié)

以上是生活随笔為你收集整理的hdu--4028--dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。