C++ 动态规划

合唱团

合唱团__牛客网

先读题★

状态表示 dp[i][j]表示第 i 个人为结尾的队列中又 j 个人的最大值，☆（状态表示是看别人的）

遇到的逻辑问题：

1. 怎么映射？映射到arr数组里，可以-1也可以不加。因为是自己输入，在最开始添加一个就行，且也多开一个

2. 可以不多开dp和数组，刚开是想的时候还是参考经验，包括多开和初始化（其实就是逻辑没有理清楚）因为第一次初始化的位置没有借助无效的位置（没有初始化过的位置），主要是慌啊，有点害怕和紧张，想快点先写一点代码

3. 比如说第i号位置的j个人，那么就去第m为结尾的 j - 1  一个里找一个最大值，

        问题1： i - d <= m <= i - 1;  m会越界，到这我就打算要扩容dp和数组了，因为i - 1对于第0个位置；其二 i - d，看例子成负数了，我第一时间想到的是修正成1（因为dp扩容）

        问题2：我发现最大值和最小值数据多了，监视里不对？因为是乘法，肯定dp里不能是0，对吧，不然一直是0了；判断代码肯定是这样的->  max(maxval[i][j], max(maxval[x][j - 1] * arr[i], minval[x][j - 1] * arr[i])); 如果第一个值是负数，不就是1了吗？对于minval来说，第一个值是正数，也会改成错误的1，那么怎么办啊？画图发现dp[i][1]（指的是maxval,minval）的位置就是arr[i],所以添加if(j == 1) 开始初始化

        问题3：还是不对第一次的这样值-> maxval[i][j] 总是会影响我判断，但是这个肯定要，因为有好多个maxval[i][j] 里找一个最大的；然后想到，不如给他初始化了，直接从i位置向前连续去j个（d起码要是1吧），这回总该对了吧

        问题4：发现，例子长了还是不对（就是逻辑问题，不全）它怎么比预期的值大？肯定是取到了不该取的值，起码不越界；就想到，比如i - d < 0 了，那么从1 到 i - 1都可以取吗？不行啊，比如说要填 j = 3 的位置 要去找j = 2，但是不能去 i = 1 （i = 1 的时候只能找一个值（下标嘛，自身往前就自己一个）（我扩容了arr））里找吧，它只有一个值啊，所以要把这范围去掉，就是因为范围变大，导致max比原来的大  x = i - d > j - 1 ? i - d，其实就是满足条件的情况下（j - 1）可以的最大差(新的d ，这个是 <= 原来的d)，这回总该对了吧

        问题5：天坑，怎么只对一半？那不是白做了吗？因为是乘法所以数据多了很可能越界（10个10就越了），数据类型要改成long long

总结：如果没有样例直接完蛋，因为逻辑不全；还是要先把思路全给理清了，是否需要初始化，怎么到算过的位置取值的（是否符合条件，是否越界，这个位置是否有效）

扩dp，arr代码：

#include <iostream>
#include <vector>
using namespace std;
int main()      
{
	int n, k, d;                         ///终于过了，改了2个小时，
	cin >> n;
	vector<int> arr(n + 1);
	arr.push_back(0);
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	cin >> k >> d;
	vector<vector<long long>> maxval(n + 1, vector<long long>(k + 1, 1));
	vector<vector<long long>> minval(n + 1, vector<long long>(k + 1, 1));
	long long ret = 0;
	for (int i = 1; i < n + 1; i++)
	{
		for (int j = 1; j < k + 1 && j <= i; j++)
		{
			if (j == 1)
			{
				maxval[i][j] = arr[i];
				minval[i][j] = arr[i];
				continue;
			}
			for (int m = i; m > i - j; m--) //保证了进去判断，不然1给我搞不会了
			{
				maxval[i][j] = maxval[i][j] * arr[m];
				minval[i][j] = minval[i][j] * arr[m];
			}
			for (int x = i - d > j - 1 ? i - d : j - 1; x <= i - 1; x++)  //开始是i - 1,其实是有不合法的区域
			{
				maxval[i][j] = max(maxval[i][j], max(maxval[x][j - 1] * arr[i], minval[x][j - 1] * arr[i]));
				minval[i][j] = min(minval[i][j], min(minval[x][j - 1] * arr[i], maxval[x][j - 1] * arr[i]));
			}
		}
		ret = max(ret, maxval[i][k]);
	}
	cout << ret;
	return 0;
}

不扩代码

int main()
{
	int n, k, d;                         
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cin >> k >> d;
	vector<vector<long long>> maxval(n, vector<long long>(k, 1));  /// 确实，做的不够多，这种乘法的肯定是要longlong的
	vector<vector<long long>> minval(n, vector<long long>(k, 1));
	long long ret = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < k && j <= i; j++)
		{
			if (j == 0)
			{
				maxval[i][j] = arr[i];
				minval[i][j] = arr[i];
				continue;
			}
			for (int m = i; m > i - j; m--) //保证了进去判断，不然1给我搞不会了
			{
				maxval[i][j] = maxval[i][j] * arr[m];
				minval[i][j] = minval[i][j] * arr[m];
			}
			for (int x = i - d > j - 1 ? i - d : j - 1; x <= i - 1; x++)  //开始是i - 1,其实是有不合法的区域
			{
				maxval[i][j] = max(maxval[i][j], max(maxval[x][j - 1] * arr[i], minval[x][j - 1] * arr[i]));
				minval[i][j] = min(minval[i][j], min(minval[x][j - 1] * arr[i], maxval[x][j - 1] * arr[i]));
			}
		}
		ret = max(ret, maxval[i][k - 1]);
	}
	cout << ret;
	return 0;
}

 马戏团

 最坑的就在这：题目没读清楚；原话：站在某个人肩上的人应该既比自己矮又比自己瘦，或相等站在某个人肩上的人应该既比自己矮又比自己瘦，或相等；指的是身高体重必须是不相同的，没怎么看就按照常理来写

代码问题：为什么体重相同的时候身高，排序会影响个数？

只会对体重相同有影响，导致这部分dp大了，间接影响后面的dp；升序加上v[j][1] >= v[i][1]可以消除相同体重不同身高的干扰

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
struct cmp3
{
	bool operator()(vector<int>& v1, vector<int>& v2)
	{
		return v1[0] > v2[0] || v1[0] == v2[0] && v1[1] < v2[1];
	}
};
int main()
{
	int n;
	while (cin >> n)
	{
		vector<vector<int>> v;
		vector<int> tmp(2);
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x >> tmp[0] >> tmp[1];
			v.push_back(tmp);
		}
		sort(v.begin(), v.end(), cmp3());
		vector<int> dp(n, 1);
		int ret = 1;
		for (int i = 1; i < v.size(); i++)
		{
			for (int j = 0; j < i; j++)
			{
				if (v[j][1] >= v[i][1]) dp[i] = max(dp[i], dp[j] + 1);
			}
			ret = max(ret, dp[i]);
		}
		cout << ret << endl;
	}
	return 0;
}

连续子数组最大和

连续子数组最大和_牛客题霸_牛客网

#define  _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<long long> arr(n);
	for (int i = 0; i < n; i++) cin >> arr[i];
	vector<long long> dp(n);
	dp[0] = arr[0];
	long long ret = dp[0];
	for (int i = 1; i < n; i++)
	{
		dp[i] = max(arr[i], dp[i - 1] + arr[i]);
		ret = max(dp[i], ret);
	}
	cout << ret;
}