最大分值问题 动态规划 C++

建立两个数组dp和sum，其中：

• dp[i][j]为前i个数分为j段时，最大的分值和

• sum[i]为前i个数的和

• dp[i][1]就是前i个数分为1段的最大分值和：

易知 d p [ i ] [ 1 ] = ( d p [ i − 1 ] [ 1 ] + a [ i ] ) m o d    p dp[i][1]=(dp[i-1][1]+a[i])mod{p} dp[i][1]=(dp[i−1][1]+a[i])modp

和 s u m [ i ] = s u m [ i − 1 ] + a [ i ] sum[i]=sum[i-1]+a[i] sum[i]=sum[i−1]+a[i]

接下来，由于分成一段的情况已经讨论，需要从j=2开始，遍历所有的分段数，对于每个分段数j,(2<=j<=m)。因为要想分为j段，则至少有j个数，所以数组长度的取值为i,(j<=i<=n)。

当j>1时，假设前k个数分为j-1段，从k+1~i为第j段，则有：

d p [ k ] [ j − 1 ] + ( s u m [ i ] − s u m [ k ] ) m o d    p dp[k][j-1]+(sum[i]-sum[k])mod{p} dp[k][j−1]+(sum[i]−sum[k])modp为前k个数分为j-1段的最大分值和。

其中 s u m [ i ] − s u m [ k ] sum[i] - sum[k] sum[i]−sum[k]为第j段的和，对其取余p即为第j段的分值。

由于前k个数分为j-1段，则k至少为j-1，取值范围是(j-1<=k<=i-1)

遍历k，取其中最大的值，即为前i个数分为j段的分值和中最大的那一个，即dp[i][j]。

由于三层循环嵌套，可知时间复杂度为 O ( m n 2 ) O(mn^2) O(mn2)

#include 
using namespace std;
#define N 105
int a[N];
int dp[N][N]; // 前i个数分为j段所得最大
int sum[N];




int getMaxSeg(int a[], int p, int m, int n)
{
	// 初始化
	for (int i = 1; i <= n; i++)
	{
		dp[i][1] = (dp[i - 1][1] + a[i]) % p;
		sum[i] = sum[i - 1] + a[i];
	}

	for (int j = 2; j <= m; j++)
	{
		for (int i = j; i <= n; i++)
		{
			int mx = -1;
			for (int k = j - 1; k < i; k++)
				mx = max(mx, dp[k][j - 1] + (sum[i] - sum[k]) % p);
			dp[i][j] = mx;
		}
	}

	return dp[n][m];
}

int main()
{
	int p, m, n;
	cin >> p >> m >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	cout << getMaxSeg(a, p, m, n);
}