当前位置：首页 > article >正文

[ABC267D] Index × A(Not Continuous ver.)

article 2025/3/4 15:36:28

解题思路

本题解介绍一种更容易理解的解法（当然，各位大佬也可以用 01 背包做）……

这是一道 DP 题……

设 $f(i,j)$ 表示前 $i$ 个数，已经选了 $j$ 个的最大和。

对于第 $i$ 个数，我们可以选 / 不选。

选：

$f(i,j)=\max(f(i-1,j-1)+a_i\times j)$

不选：

$f(i,j)=\max(f(i-1,j))$

注意：是长度为 M 的序列！不是长度小于 M 的序列！

然后直接 DP，取 $f(i,m)$ 的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

int f[2001][2001],n,m,a[2001];
int ans=-1e16;

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	
	memset(f,-0x3f,sizeof f);
	f[1][1]=a[1];
	f[1][0]=0;
	ans=f[1][m];
	for(int i=2;i<=n;i++)
	{
		f[i][0]=f[i-1][0];
		for(int j=1;j<=min(i,m);j++)
		{
			f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i]*j);
			ans=max(ans,f[i][m]);
		}
	//	ans=max(ans,f[i][0]);
	}
	cout<<ans;
}

查看全文

http://www.kler.cn/a/428104.html