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

D

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

思考：

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

直接二维：
#include
#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
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

总结：
一定要搞清楚自己的dp状态定义，要确定好细节。