USACO Buy Low, Buy Lower 解题报告-白红宇

USACO Buy Low, Buy Lower 解题报告

阅读量：4204 次

发布时间：2019-05-26

本文共 1830 字，大约阅读时间需要 6 分钟。

这道题前部分是求最长递减子序列，后部分是求不同的最长递减子序列的个数。前者利用二分查找有O(nlogn)的时间复杂度，但由于后者决定了整体的时间复杂度，故这里没有采用这样的优化。后者如果不考虑“不同”，则为简单的动态规划，把在这个元素之前能够“续”一个的序列数目加起来就可以。当考虑“不同”的时候需要仔细考虑下，实际上，假设以当前元素结束的最长递减子序列长度为pos，那么之前所有与该元素具有相同pos的元素，如果值相同，应该是连续出现的，即中间不会有个元素值不同。考虑下pos为以当前元素结束的最长递减子序列长度可以立刻得出这样的结论。这也是标准答案采用的方法。

/* ID: thestor1 LANG: C++ TASK: buylow */#include 
   
      #include 
    
       #include 
     
        #include 
      
         #include 
       
          #include 
        
          #include 
         
           #include 
          
            #include 
           
            #include 
             #include 
             
               #include 
              
                #include 
               
                using namespace std;string sum_str(string str1, string str2){ string ret(max(str1.size(), str2.size()), '0'); int i = str1.size() - 1, j = str2.size() - 1, k = ret.size() - 1, carry = 0, sum = 0; while (i >= 0 && j >= 0) { sum = carry + str1[i] - '0' + str2[j] - '0'; ret[k] = (sum % 10) + '0'; carry = sum / 10; i--; j--; k--; } while (i >= 0) { sum = carry + str1[i] - '0'; ret[k] = (sum % 10) + '0'; carry = sum / 10; i--; k--; } while (j >= 0) { sum = carry + str2[j] - '0'; ret[k] = (sum % 10) + '0'; carry = sum / 10; j--; k--; } assert(k == -1); if (carry) { ret = "1" + ret; } return ret;}int main(){ sum_str("16", "4"); FILE *fin = fopen("buylow.in", "r"); FILE *fout = fopen("buylow.out", "w"); int N; fscanf(fin, "%d", &N); std::vector
                
                  prices; for (int i = 0; i < N; ++i) { int p; fscanf(fin, "%d", &p); prices.push_back(p); } int L = 0; std::vector
                 
                   pos(N, 1); for (int i = 0; i < N; ++i) { for (int j = 0; j < i; ++j) { if (prices[j] > prices[i]) { if (pos[j] + 1 > pos[i]) { pos[i] = pos[j] + 1; } } } if (pos[i] > L) { L = pos[i]; } } // cout<<"L:"<
                  
                   <
                   
                     cnt(N, "1"); for (int i = 0; i < N; ++i) { if (pos[i] != 1) { cnt[i] = "0"; } for (int j = 0; j < i; ++j) { if (prices[j] > prices[i] && pos[j] + 1 == pos[i]) { // cout<<"[debug]"<
                    
                     <<"+"<
                     
                      <<"="; cnt[i] = sum_str(cnt[i], cnt[j]); // cout<<"[debug]"<
                      
                       <

转载地址：http://zbxli.baihongyu.com/

你可能感兴趣的文章