HDU4570 Multi-bit Trie 区间DP - c++编程基础

TOP

HDU4570 Multi-bit Trie 区间DP

2015-07-20 18:07:20 来源: 作者: 【大中小】浏览:6次

题意：这题题意确实有点难懂，起码对于我这个英语渣渣来说是这样，于是去别人的博客看了下题目意思，归纳起来如下：

给出一个长度为n的数列，将其分成若干段，要求 data-cke-saved-src=https://www.cppentry.com/upload_files/article/49/1_avfzt__.png 最小，其中ai是每一段数列的第一项，bi是每一段的长度，l为将数列分成l段。

比如样例：n=7，A={1 2 4 4 5 4 3}，将其分成1 2 4| 4 5| 4| 3，则其所用空间为1*2^3+4*2^2+4*2^1+3*2^1=38，而如果分成1 2| 4 4 5| 4 3，则其所用空间为1*2^2+4*2^3+4*2^2=52，比38大。

本弱菜见解：

分成数段，而且每段的求和的值在这一段元素中只与第一个元素值有关，还有就是跟这段长度有关，所以区间DP做起来比较清晰，做区间DP一向不太喜欢直接来推一把，喜欢记忆化搜索的来一把，只与头元素有关，那么一层一层搜下去，不是很复杂的dfs过程

dp[i]表示以元素num[i]为开头的最小的那个什么值，

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; ll num[100 + 56]; ll dp[100 + 56]; int n; void init() { memset(num,0,sizeof(num)); memset(dp,-1,sizeof(dp)); } ll dfs(int x) { if(x == n+1)return 0; if(dp[x] != -1)return dp[x]; dp[x] = INF; for(int i=x+1;i<=min(x + 20,n + 1);i++) dp[x] = min(dp[x],dfs(i) + num[x] * (1ll<<(i - x))); return dp[x]; } int main() { int t; scanf(%d,&t); while(t--) { init(); scanf(%d,&n); ll ans = 0ll; for(int i=1;i<=n;i++) { scanf(%I64d,&num[i]); ans += 2 * num[i]; } ll ans1 = dfs(1); ans = min(ans,ans1); printf(%I64d ,ans); } return 0; }

记忆化搜索是向下一层一层找的，那么在直接推的时候我也是想着一个一个往后推此时所得到的最优解，意思就是dp[i]表示从第一个推到第i个的时候最优解，还需要一层循环j来枚举前i个的最后一段的长度为j的所有结果中寻找最优解

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; ll num[100 + 56]; ll dp[100 + 56]; int n; void init() { memset(num,0,sizeof(num)); } int main() { int t; scanf(%d,&t); while(t--) { init(); scanf(%d,&n); ll ans = 0ll; for(int i=1;i<=n;i++) scanf(%I64d,&num[i]); for(int i=1;i<=n;i++) { dp[i] = INF; for(int j=1;j<=i;j++) { if(j > 20)break; dp[i] = min(dp[i],dp[i - j] + num[i - j + 1] * (1ll<
                    
                     ?
                      好了都搞定以后呢，看了一下别人的做法，发现有二维的，蒽一般来说二维的比一维的要更加清晰，更加容易理解，更加好推一点，但是这道题目因为只跟 第一个元素有关系 所以一维的也很清晰的，就稍微看了想了一下二维的 ，没有写，后来又看到一个大神说用迭代的比较快，看着他的代码主要思想，就是直接从后往前推，我的这个最后结果为dp[n]，那么他的 最后就在dp[1]与 分n段中取最优，大神说迭代的 比记忆化搜索要快一点，于是按照那个思想 敲了一下，还敲错了 两把，汗颜，大神就是大神，可是敲完发现 我前面两个过的都是0ms,迭代反而 变成了 15ms，汗颜，后来又多交了几把，发现也变成了0ms，是HDOJ的问题， 想想应该迭代的比较快
                     ?
                     ?
                     #include
                      
                       
#include
                       
                         #include
                        
                          #include
                         
                           #include
                          
                            #include
                           
                             #include
                            
                              #include
                             
                               #include
                               #include
                               
                                 #include
                                
                                  #include
                                 
                                   #include
                                  
                                    #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
                                   
                                     > G; //typedef pair
                                    
                                      P; //vector
                                     
                                       > ::iterator iter; // //map
                                      
                                       mp; //map
                                       
                                        ::iterator p; ll num[100 + 56]; ll dp[100 + 56]; void init() { memset(num,0,sizeof(num)); memset(dp,0,sizeof(dp)); } int main() { int t; scanf(%d,&t); while(t--) { init(); int n; scanf(%d,&n); ll ans = 0ll; for(int i=1;i<=n;i++) { scanf(%I64d,&num[i]); ans += 2 * num[i];//分n段 } dp[n] = 2 * num[n]; for(int i=n-1;i>0;i--) { dp[i] = INF; for(int j=i+1;j<=n+1;j++) { if(j > i + 20)break; dp[i] = min(dp[i],dp[j] + num[i] * (1ll<
                                        
                                         ?
                                         ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：ZOJ 3324 Machine	下一篇：HDU 1232：畅通问题（并查集）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: