荣誉艾尔迪亚人的题解

目录

原题描述：

题目背景

题目描述

输入格式

输出格式

样例

Input 1

Output 1

Input 2

Output 2

数据范围：

样例解释

主要思路：

代码code：

---

原题描述：

时间限制: 1000ms

空间限制: 65536kb

题目背景

---

? 艾尔迪亚人在与巨人的战斗中雷枪发挥了不可磨灭的作用，雷枪之所以能够发挥那么强的作用，是因为雷枪能够牢固的刺入巨人的身体内引爆。雷枪的核心威力来源自火药，而火药的原材料由硫磺、硝石与炭原材料制造而成的，而火药的原材料可以由矿洞产出。

题目描述

---

?小埋是一个艾尔迪亚矿工，挖矿对于小埋来说能获得财富和荣誉（因为要抗击巨人需要大量材料，艾尔迪亚高层要鼓励矿工们多采矿），荣誉值到达一定值可以成为荣誉艾尔迪亚人。

? 现在小埋挖矿既想获得一定的财富也想获得一定量的荣誉。假设我们已知小埋挖的那部分矿洞有??块矿石，并且已知这??块矿石的重量?，对于每块矿石我们能够获得一些财富值和荣誉值，对于每块矿石的财富值和荣誉值设定如下。

• 对于第块矿石，它的财富值为前?块矿石中以第??块矿石结尾的(非严格)递增序列长度最大值。（第?块矿石为结尾矿石，就是必须选第?块矿石为结尾）。
• 对于第??块矿石，它的荣誉值为第??块到第??块矿石中以第???块矿石为起点的(非严格)递减序列长度最大值。（第?块矿石为起点矿石，就是必须选第?块矿石为起点）。

小埋想要在自己需要至少获得财富值为??荣誉值为?的情况下，所挖出矿石总和的最小重量。

输入格式

? 第一行输入一个整数??,表示矿石的数量。

? 第二行??个整数??分别表示每个矿石的重量。

? 第三行输入?和??表示我们需要至少获得的财富值和荣誉值。

输出格式

输出占一行，输出一个整数，表示?输出小埋能够在限定条件下，挖出矿石总和的最小重量。

样例

Input 1

5
1 2 2 3 5
5 5

Output 1

8

Input 2

5
1 2 3 2 1
3 4 

Output 2

3

数据范围：

对于所有测试数据有：。

样例解释

• 对于样例1，我们可以选择前四个矿石。
  • 以第一个矿石为结尾的(非严格)递增序列为?,财富值为?,以第一个矿石为开头的非严格递减序列为,荣誉值为?。
  • 以第二个矿石为结尾的非严格递增序列为?,财富值为,以第二个矿石为开头的非严格递减子序列为?,荣誉值为?。
  • 以第三个矿石为结尾的非严格递增序列为?,财富值为,以第三个矿石为开头的非严格递减子序列为?，荣誉值为。
  • 以第四个矿石为结尾的非严格递增序列为,财富值为,以第四个矿石为开头的非严格递减子序列为,荣誉值为?。
  • 所以我们的财富值为?,荣誉值为,满足我们所需的至少获得财富值为?,荣誉值为?,并且所挖去的矿石总重量最小。
• 对于样例2，我们可以选第二个矿石和第五个矿石，第二个矿石重量为?,财富值为?荣誉值为,第五个矿石重量矿石重量为?,财富值为?,荣誉值为，我们此时满足至少财富值,且荣誉值为?的情况，并且此时总重量最小为?,或者我们也可以选择第一块矿石和第二块矿石。

主要思路：

很明显，是最长上升子序列问题+二维费用背包问题。

把第??块到第??块矿石中以第???块矿石为起点的(非严格)递减序列长度最大值。（第?块矿石为起点矿石，就是必须选第?块矿石为起点）这句话就理解成第i块矿石为结尾，第n块矿石为开头的最长上升子序列，接着后面就是二维费用背包。

但是最长上升子序列朴素版是,这里会超时，所以得用二分优化成

代码code：

#include<bits/stdc++.h>
using namespace std;
long long tmp[100010],f[100010],f1[100010],a[100010];
long long n;
long long m,v;
long long dp[1010][1010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>m>>v;
	long long pos=1;
	tmp[1] = a[1];
	f[1] = 1;
	for(int i=2;i<=n;i++)
	{
		long long l=1,r=pos;
		while(l<r)
		{
			long long mid = (l+r+1)/2;
			if(tmp[mid]<=a[i])
			{
				l = mid;
			}
			else
			{
				r = mid-1;
			}
		}
		if(tmp[l]>a[i])
		{
			tmp[l] = a[i];
			f[i] = l;
		}
		else
		{
			if(l == pos)
			{
				tmp[++pos] = a[i];
				f[i] = pos;
			}
			else
			{
				tmp[l+1] = a[i];
				f[i] = l+1;
			}
		}
	}
	//此时，f[i]就代表已第i个为结尾，第一个为开头的最长上升子序列
	pos=1;
	tmp[1] = a[n];
	f1[n] = 1;
	for(int i=n-1;i>=1;i--)
	{
		long long l=1,r=pos;
		while(l<r)
		{
			long long mid = (l+r+1)/2;
			if(tmp[mid]<=a[i])
			{
				l = mid;
			}
			else
			{
				r = mid-1;
			}
		}
		if(tmp[l]>a[i])
		{
			tmp[l] = a[i];
			f1[i] = l;
		}
		else
		{
			if(l == pos)
			{
				tmp[++pos] = a[i];
				f1[i] = pos;
			}
			else
			{
				tmp[l+1] = a[i];
				f1[i] = l+1;
			}
		}
	}
	//同理
	memset(dp,0x3f,sizeof(dp));//dp初始化
	dp[0][0] = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(int k=v;k>=0;k--)
			{
				dp[j][k] = min(dp[j][k],dp[max(j-f[i],0LL)][max(k-f1[i],0LL)]+a[i]);//二维费用背包
			}
		}
	}
	cout<<dp[m][v];
	return 0;
}