正题

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

---

题目大意

求序列A有多少个长度为M的递增子序列。

---

解题思路

用fi,jfi,j表示长度为i，以AjAj结尾的序列的个数。然后显然得出动态转移方程通过上一次从任意一个地方转移，动态转移方程：

$$f_{i,j}=\sum_{k<j,A_k <br /> 我们可以用树状数组储存和维护k。 <p></p> <hr /> <h2 id="code">code</h2> <span class="hljs-preprocessor">#include&lt;cstdio&gt;</span> <span class="hljs-preprocessor">#include&lt;algorithm&gt;</span> <span class="hljs-preprocessor">#include&lt;cstring&gt;</span> <span class="hljs-preprocessor">#define N 2010</span> <span class="hljs-preprocessor">#define lowbit(x) x&amp;-x</span> <span class="hljs-preprocessor">#define BPM 1000000007</span> <span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>; <span class="hljs-keyword">int</span> t[N],a[N],f[N][N],n,m,l,uiqe[N],ans,ts; <span class="hljs-keyword">void</span> change(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> k) {<span class="hljs-keyword">while</span>(x&lt;&#61;l){t[x]&#61;(t[x]&#43;k)%BPM;x&#43;&#61;lowbit(x);} } <span class="hljs-keyword">int</span> ask(<span class="hljs-keyword">int</span> x) {<span class="hljs-keyword">int</span> sum&#61;<span class="hljs-number">0</span>;<span class="hljs-keyword">while</span>(x){sum&#61;(sum&#43;t[x])%BPM;x-&#61;lowbit(x);}<span class="hljs-keyword">return</span> sum; } <span class="hljs-keyword">int</span> main() {<span class="hljs-built_in">scanf</span>(<span class="hljs-string">&#34;%d&#34;</span>,&amp;ts);<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> ti&#61;<span class="hljs-number">1</span>;ti&lt;&#61;ts;ti&#43;&#43;){<span class="hljs-built_in">scanf</span>(<span class="hljs-string">&#34;%d%d&#34;</span>,&amp;n,&amp;m);a[<span class="hljs-number">0</span>]&#61;-<span class="hljs-number">2147483647</span>;uiqe[n&#43;<span class="hljs-number">1</span>]&#61;a[<span class="hljs-number">0</span>];<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i&#61;<span class="hljs-number">1</span>;i&lt;&#61;n;i&#43;&#43;)<span class="hljs-built_in">scanf</span>(<span class="hljs-string">&#34;%d&#34;</span>,&amp;a[i]),uiqe[i]&#61;a[i];sort(uiqe&#43;<span class="hljs-number">1</span>,uiqe&#43;<span class="hljs-number">2</span>&#43;n);l&#61;unique(uiqe&#43;<span class="hljs-number">1</span>,uiqe&#43;<span class="hljs-number">1</span>&#43;n)-(uiqe&#43;<span class="hljs-number">1</span>);<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i&#61;<span class="hljs-number">0</span>;i&lt;&#61;n;i&#43;&#43;)a[i]&#61;lower_bound(uiqe&#43;<span class="hljs-number">1</span>,uiqe&#43;<span class="hljs-number">1</span>&#43;l,a[i])-uiqe;<span class="hljs-comment">//以上为离散化</span><span class="hljs-built_in">memset</span>(f,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span>(f));f[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>]&#61;<span class="hljs-number">1</span>;ans&#61;<span class="hljs-number">0</span>;<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i&#61;<span class="hljs-number">1</span>;i&lt;&#61;m;i&#43;&#43;){<span class="hljs-built_in">memset</span>(t,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span>(t));change(a[<span class="hljs-number">0</span>],f[i-<span class="hljs-number">1</span>][<span class="hljs-number">0</span>]);<span class="hljs-comment">//修改</span><span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j&#61;<span class="hljs-number">1</span>;j&lt;&#61;n;j&#43;&#43;){f[i][j]&#61;ask(a[j]-<span class="hljs-number">1</span>);<span class="hljs-comment">//询问和</span>change(a[j],f[i-<span class="hljs-number">1</span>][j]);<span class="hljs-comment">//维护和</span><span class="hljs-keyword">if</span>(i&#61;&#61;m) ans&#61;(ans&#43;f[i][j])%BPM;}}<span class="hljs-built_in">printf</span>(<span 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="//cdnjs.cloudflare.com/ajax/libs/highlight.js/11.6.0/highlight.min.js">$$