HDU 2639 Bone Collector II / 第K大的01双肩包

HDU 2639 Bone Collector II / 第K大的01背包

第k大可以多加一维状态

对于第i个物品 每次求出不放这个物品的时候 第1到第k大的数 就是上一维的情况 再求出放这个物品时候第1到第k大的数 得到2*k个价值 求出2*k个数中最大的k个

然后题目要求严格递减 不能一样

#include <cstdio>
#include <cstring>
const int maxn = 110;
int dp[maxn][maxn*10][33];
int a[maxn], b[maxn];
int x[maxn], y[maxn];
int main()
{
	int T;
	int n, m, t;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d %d", &n, &m, &t);
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		for(int i = 1; i <= n; i++)
			scanf("%d", &b[i]);
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= n; i++)
		{
			for(int j = 0; j <= m; j++)
			{
				if(j < b[i])
				{
					for(int k = 1; k <= t; k++)
					{
						dp[i][j][k] = dp[i-1][j][k];
					}
				}
				else
				{
					for(int k = 1; k <= t; k++)
					{
						x[k] = dp[i-1][j-b[i]][k]+a[i];
						y[k] = dp[i-1][j][k];
					}
					x[t+1] = y[t+1] = -1000000;
					int i1 = 1, i2 = 1, i3 = 1;
					while(i1 <= t && (i2 <= t || i3 <= t))
					{
						if(x[i2] > y[i3])
						{
							dp[i][j][i1] = x[i2];
							i2++;
						}
						else
						{
							dp[i][j][i1] = y[i3];
							i3++;
						}
						if(dp[i][j][i1] != dp[i][j][i1-1])
							i1++;
					}
				}
			}
		}
		printf("%d\n", dp[n][m][t]);
	}
	return 0;
}