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

ABC-Index-(dp枚举方式优化)

news 来源：原创 2024/5/4 5:35:38

题意：
就是给你一个数组，让你选一个长度为m的子序列，然后这个长度为m的子序列为vb数组，那么这个价值为i*vb[i]的总和。

思考：

这题有个简单版本就是连续数组，那么就直接每次拿一个仍一个，维护总和ans，一直更新最大值就可以了。
那么这个可以不连续的，n和m也都变成了2e3。那么很明显就只能dp了，最经典的dp定义就是dp[i][j]为到了第i个数字，取了j个数的价值。然后i从k转移再枚举一次，但是这样是O(n³)复杂度。
但是想到j只能用到j-1对吧，又是经典的优化。和这两题一样：CFdiv2-Chip Move 、牛客多校-Two Frogs。然后就写了，第一维枚举选的第几个数，然后第二维枚举第i个点，那么dp[i]这一层可以更新下一层>=i的所有点，所以我就从前往后一直维护一个最大值就可以了。那么下一层的dp[i] = 这一层的前缀maxn+贡献。最后处理完对dp每个点取一个最大值就可以了。
但是发现例子：-1 -2 - 3 -4，是不对的。因为dp本来的状态应该是到第i个点，选了恰好j个数的代价，所以只有dp[0][0] = 0,剩下的都是-inf，但是我如果把第二维度优化掉，这样就会让dp[0][0-m] = 0了，这样就多了。所以可以对dp开二维，当然也可以只开dp和tp，但是maxn为0的时候只有最刚开始的时候。

直接二维：
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;
 
int T,n,m,k;
int va[N];
int dp[M][M];
 
signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		dp[i][j] = -inf;
	}
	dp[0][0] = 0;
	for(int j=0;j<m;j++)
	{
		int maxn = -inf;
		for(int i=0;i<=n;i++)
		{
			dp[i][j+1] = maxn+(j+1)*va[i];
			maxn = max(maxn,dp[i][j]);
		}
	}
	int maxn = -inf;
	for(int i=1;i<=n;i++) maxn = max(maxn,dp[i][m]);
	cout<<maxn<<"\n";
	return 0;
}
滚动数组特判：
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
int dp[M];
int tp[M];

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=0;i<=n;i++) dp[i] = tp[i] = -inf;
	for(int j=0;j<m;j++)
	{
		int maxn = -inf;
		if(j==0) maxn = 0; //只有i==0&&j==0也就是第一次的时候maxn = 0
		for(int i=0;i<=n;i++)
		{
			tp[i] = maxn+(j+1)*va[i];
			maxn = max(maxn,dp[i]);
		}
		for(int i=1;i<=n;i++) dp[i] = tp[i];
	}
	int maxn = -inf;
	for(int i=1;i<=n;i++) maxn = max(maxn,dp[i]);
	cout<<maxn<<"\n";
	return 0;
}