（2022牛客多校四）A-Task Computing （排序+动态规划）

题目：

样例输入：

5 2
1 2 3 4 5
12000 11000 10000 9000 8000

 样例输出：

8.5000000000000000

题意：从n个任务中选m个(a1,a2,……,am)出来并任意排序，收益是

 求最大收益。

看到公式的下标分布就知道这个值是跟任务的顺序有关的，所以我们应该先考虑按照什么样的顺序进行排序，一般常见的方法都是逐步调整法，就是说先假设一种顺序，然后交换其中两个相邻元素的位置，算出来两种排序方式对应的答案，进行比较就可以知道按照什么进行排序了！

下面是调整的过程：

我们先对n个任务按照上述方式进行排序，那么从里面任意选出来m个都是满足上述排序规则的，所以问题就转化为了我们如何从n个任务中选出来m个任务。

我一开始想的是利用f[i][j]表示前i个任务中选出j个任务所能得到的最大值，再利用一个mul[i][j]表示达到f[i][j]状态时的乘积，然后递推方程就是:

f[i][j]=max(f[i-1][j],f[i-1][j-1]+w[i]*mul[i-1][j-1])，再更新一下mul数组

但是后来发现这样是存在问题的，原因就在于我们从前i个任务中选j个任务所能得到的最大值并不一定是从前i-1个任务中选j-1个任务或者选j个任务得到的最大值，因为对于从前i-1个任务中选取的任务数不同会直接影响所选取任务的乘积，那么这个是会对答案造成很大影响的，所以不能这么做。

正解：

之所以我们刚才考虑的那种动态转移方程不行就是因为后面的值取决于前面的两个值，一个是乘积另一个是和式，所以我们无法直接根据和式的值来向后转移，但是通过上面的公式变形后我们可以清楚的发现，我们可以从后往前推导，这样前面值只跟后面的和式有关，而不再与乘积有关，这样我们就可以进行动态转移了，只是更新方式会略有变化，这种方法还是挺妙的。

设f[i][j]表示考虑第i~n个任务选出来j个任务的最大值，然后我们直接倒序更新该数组

动态转移方程：f[i][j]=max(f[i+1][j],f[i+1][j-1]*p[i].q+p[i].w)

下面是代码：

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll; 
const int N=1e5+10;
struct node{
	ll w;
	double q;
}p[N];
double f[N][30];//f[i][j]表示考虑第i~n个任务选出来m个任务的最大值
bool cmp(node a,node b)
{
	return (a.w-b.q*a.w+a.q*b.w-b.w)>=0;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%lld",&p[i].w);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf",&p[i].q);
		p[i].q/=10000;
	}
	sort(p+1,p+n+1,cmp);
	for(int i=n;i>=1;i--)
	for(int j=1;j<=m;j++)
		f[i][j]=max(f[i+1][j],f[i+1][j-1]*p[i].q+p[i].w);
	printf("%.8lf",f[1][m]);
	return 0;
}