hdu 2639 第k大01背包

hdu 2639 第k大01背包

					<div> 
														 战亿熊猫															
														 2024-08-31 02:35:44 

				</div>
									<pre>/*<br/>

HDU 2639
求01背包的第k大解。
合并两个有序序列
*/ #include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=;
int dp[][];//dp[i][j]表示容量为i,第j大的值
int value[MAXN];
int weight[MAXN]; int a[];
int b[]; int N,V,K; void DP()
{

memset(dp,,sizeof(dp));<br/>
for(int i=;i&lt;N;i++)<br/>
   for(int j=V;j&gt;=value[i];j--)<br/>
   {<br/>
       for(int k=;k&lt;=K;k++)<br/>
       {<br/>
           a[k]=dp[j][k];<br/>
           b[k]=dp[j-value[i]][k]+weight[i];<br/>
       }<br/>
       int x,y,z;<br/>
       x=y=z=;<br/>
       a[K+]=b[K+]=-;//这个一定要<br/>
       while(z&lt;=K&amp;&amp;(x&lt;=K||y&lt;=K))//合并两个已经排好序的序列<br/>
       {<br/>
           if(a[x]&gt;b[y])dp[j][z]=a[x++];//注意相同的只算一个<br/>
           else dp[j][z]=b[y++];<br/>
           if(dp[j][z]!=dp[j][z-])z++;<br/>
       }<br/>
   }<br/>

}
int main()
{

int T;<br/>
scanf(&#34;%d&#34;,&amp;T);<br/>
while(T--)<br/>
{<br/>
    scanf(&#34;%d%d%d&#34;,&amp;N,&amp;V,&amp;K);<br/>
    for(int i=;i&lt;N;i++)scanf(&#34;%d&#34;,&amp;weight[i]);<br/>
    for(int i=;i&lt;N;i++)scanf(&#34;%d&#34;,&amp;value[i]);<br/>
    DP();<br/>
    printf(&#34;%d\n&#34;,dp[V][K]);<br/>
}<br/>
return ;<br/>

}

														<div>