正題

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=5542

---

題目大意

求序列A有多少個長度為M的遞增子序列。

---

解題思路

用fi,jfi,j表示長度為i，以AjAj結尾的序列的個數。然后顯然得出動態轉移方程通過上一次從任意一個地方轉移，動態轉移方程：

fi,j=∑k<j,Ak<Ajfi?1,kfi,j=∑k<j,Ak<Ajfi?1,k $$f_{i,j}=\sum_{k<j,A_k <br /> 我們可以用樹狀數組儲存和維護k。 <p></p> <hr /> <h2 id="code">code</h2> <span id="ze8trgl8bvbq" class="hljs-preprocessor">#include&lt;cstdio&gt;</span> <span id="ze8trgl8bvbq" class="hljs-preprocessor">#include&lt;algorithm&gt;</span> <span id="ze8trgl8bvbq" class="hljs-preprocessor">#include&lt;cstring&gt;</span> <span id="ze8trgl8bvbq" class="hljs-preprocessor">#define N 2010</span> <span id="ze8trgl8bvbq" class="hljs-preprocessor">#define lowbit(x) x&amp;-x</span> <span id="ze8trgl8bvbq" class="hljs-preprocessor">#define BPM 1000000007</span> <span id="ze8trgl8bvbq" class="hljs-keyword">using</span> <span id="ze8trgl8bvbq" class="hljs-keyword">namespace</span> <span id="ze8trgl8bvbq" class="hljs-built_in">std</span>; <span id="ze8trgl8bvbq" class="hljs-keyword">int</span> t[N],a[N],f[N][N],n,m,l,uiqe[N],ans,ts; <span id="ze8trgl8bvbq" class="hljs-keyword">void</span> change(<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> x,<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> k) {<span id="ze8trgl8bvbq" class="hljs-keyword">while</span>(x&lt;&#61;l){t[x]&#61;(t[x]&#43;k)%BPM;x&#43;&#61;lowbit(x);} } <span id="ze8trgl8bvbq" class="hljs-keyword">int</span> ask(<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> x) {<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> sum&#61;<span id="ze8trgl8bvbq" class="hljs-number">0</span>;<span id="ze8trgl8bvbq" class="hljs-keyword">while</span>(x){sum&#61;(sum&#43;t[x])%BPM;x-&#61;lowbit(x);}<span id="ze8trgl8bvbq" class="hljs-keyword">return</span> sum; } <span id="ze8trgl8bvbq" class="hljs-keyword">int</span> main() {<span id="ze8trgl8bvbq" class="hljs-built_in">scanf</span>(<span id="ze8trgl8bvbq" class="hljs-string">&#34;%d&#34;</span>,&amp;ts);<span id="ze8trgl8bvbq" class="hljs-keyword">for</span>(<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> ti&#61;<span id="ze8trgl8bvbq" class="hljs-number">1</span>;ti&lt;&#61;ts;ti&#43;&#43;){<span id="ze8trgl8bvbq" class="hljs-built_in">scanf</span>(<span id="ze8trgl8bvbq" class="hljs-string">&#34;%d%d&#34;</span>,&amp;n,&amp;m);a[<span id="ze8trgl8bvbq" class="hljs-number">0</span>]&#61;-<span id="ze8trgl8bvbq" class="hljs-number">2147483647</span>;uiqe[n&#43;<span id="ze8trgl8bvbq" class="hljs-number">1</span>]&#61;a[<span id="ze8trgl8bvbq" class="hljs-number">0</span>];<span id="ze8trgl8bvbq" class="hljs-keyword">for</span>(<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> i&#61;<span id="ze8trgl8bvbq" class="hljs-number">1</span>;i&lt;&#61;n;i&#43;&#43;)<span id="ze8trgl8bvbq" class="hljs-built_in">scanf</span>(<span id="ze8trgl8bvbq" class="hljs-string">&#34;%d&#34;</span>,&amp;a[i]),uiqe[i]&#61;a[i];sort(uiqe&#43;<span id="ze8trgl8bvbq" class="hljs-number">1</span>,uiqe&#43;<span id="ze8trgl8bvbq" class="hljs-number">2</span>&#43;n);l&#61;unique(uiqe&#43;<span id="ze8trgl8bvbq" class="hljs-number">1</span>,uiqe&#43;<span id="ze8trgl8bvbq" class="hljs-number">1</span>&#43;n)-(uiqe&#43;<span id="ze8trgl8bvbq" class="hljs-number">1</span>);<span id="ze8trgl8bvbq" class="hljs-keyword">for</span>(<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> i&#61;<span id="ze8trgl8bvbq" class="hljs-number">0</span>;i&lt;&#61;n;i&#43;&#43;)a[i]&#61;lower_bound(uiqe&#43;<span id="ze8trgl8bvbq" class="hljs-number">1</span>,uiqe&#43;<span id="ze8trgl8bvbq" class="hljs-number">1</span>&#43;l,a[i])-uiqe;<span id="ze8trgl8bvbq" class="hljs-comment">//以上為離散化</span><span id="ze8trgl8bvbq" class="hljs-built_in">memset</span>(f,<span id="ze8trgl8bvbq" class="hljs-number">0</span>,<span id="ze8trgl8bvbq" class="hljs-keyword">sizeof</span>(f));f[<span id="ze8trgl8bvbq" class="hljs-number">0</span>][<span id="ze8trgl8bvbq" class="hljs-number">0</span>]&#61;<span id="ze8trgl8bvbq" class="hljs-number">1</span>;ans&#61;<span id="ze8trgl8bvbq" class="hljs-number">0</span>;<span id="ze8trgl8bvbq" class="hljs-keyword">for</span>(<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> i&#61;<span id="ze8trgl8bvbq" class="hljs-number">1</span>;i&lt;&#61;m;i&#43;&#43;){<span id="ze8trgl8bvbq" class="hljs-built_in">memset</span>(t,<span id="ze8trgl8bvbq" class="hljs-number">0</span>,<span id="ze8trgl8bvbq" class="hljs-keyword">sizeof</span>(t));change(a[<span id="ze8trgl8bvbq" class="hljs-number">0</span>],f[i-<span id="ze8trgl8bvbq" class="hljs-number">1</span>][<span id="ze8trgl8bvbq" class="hljs-number">0</span>]);<span id="ze8trgl8bvbq" class="hljs-comment">//修改</span><span id="ze8trgl8bvbq" class="hljs-keyword">for</span>(<span id="ze8trgl8bvbq" class="hljs-keyword">int</span> j&#61;<span id="ze8trgl8bvbq" class="hljs-number">1</span>;j&lt;&#61;n;j&#43;&#43;){f[i][j]&#61;ask(a[j]-<span id="ze8trgl8bvbq" class="hljs-number">1</span>);<span id="ze8trgl8bvbq" class="hljs-comment">//詢問和</span>change(a[j],f[i-<span id="ze8trgl8bvbq" class="hljs-number">1</span>][j]);<span id="ze8trgl8bvbq" class="hljs-comment">//維護和</span><span id="ze8trgl8bvbq" class="hljs-keyword">if</span>(i&#61;&#61;m) ans&#61;(ans&#43;f[i][j])%BPM;}}<span id="ze8trgl8bvbq" class="hljs-built_in">printf</span>(<span id="ze8trgl8bvbq" class="hljs-string">&#34;Case #%d: %d\n&#34;</span>,ti,ans);} } <h2>總結</h2> <p> 以上是<a href="/">&#x751F;&#x6D3B;&#x968F;&#x7B14;</a>為你收集整理的<a title="HDOJ5542-The Battle of Chibi&#x3010;&#x6811;&#x72B6;&#x6570;&#x7EC4;,dp&#x3011;" href="/content/870004.html">HDOJ5542-The Battle of Chibi&#x3010;&#x6811;&#x72B6;&#x6570;&#x7EC4;,dp&#x3011;</a>的全部內容，希望文章能夠幫你解決所遇到的問題。 </p> <p> 如果覺得<a href="/">&#x751F;&#x6D3B;&#x968F;&#x7B14;</a>網站內容還不錯，歡迎將<a href="/">&#x751F;&#x6D3B;&#x968F;&#x7B14;</a>推薦給好友。 </p> <script src="http://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.6.0/highlight.min.js">$$