cf场+线性dp

Problem - B - Codeforces

思路：

这其实是一道数学题（最开始一直在枚举，服啦）

我们的目的是求最大利润

当a>=b是时直接令k=0,利润=n*a即可

当a<b时存在两种情况：

1.b-a>=n即所有b-i+1的情况都>a，这个时候我们把b-i+1看成一个等差数列求和即可

2.n>b-a>0这种情况我们还需要考虑到使用到的a，在此之前我们按照等差数列出售了(b-a)个，那么剩下n-(b-a)个我们则需要按照a来出售

还可以参考我觉得挺好的一篇题解：

题解：CF1978B New Bakery-CSDN博客

AC代码：

void solve()
{
	ll n, a, b, ans;
	cin >> n >> a >> b;
	if (a >= b)
	{
		cout << a * n << endl;
		return;
	}
	else
	{
		ll k = min(n, b - a);
		cout << (b + b - k + 1) * k / 2 + a * (n - k) << endl;
		return;
	}
	return;
}

Problem - B - Codeforces

思路：

采用双指针，一个指向a的头部，一个指向b的头部，两者开始进行匹配，若相同则b往下走一位，否则就终止

AC代码：

void solve()
{
	ll n, m;
	cin >> n >> m;
	cin >> a >> b;
	a = " " + a, b = " " + b;//相当于char a[],然后cin>>a+1
	ll sum = 0, j = 1;
	for (int i = 1; i <= n; i++)
	{
		for (; j <= m; j++)
		{
			if (a[i] == b[j])
			{
				sum++;
				j++;
				break;
			}
		}
		if (j > m)
			break;
	}
 
	cout << sum << endl;
	return;
}

还有一篇动态规划的题解我感觉也不错

Prefiquence(双指针,动态规划)-CSDN博客

代码奉上：

void solve()
{
	ll n, m;
	cin >> n >> m;
	cin >> a >> b;
	a = " " + a, b = " " + b;
	dp[1] = (a[1] == b[1] ? 1 : 0);
	for (int i = 2; i <= m; i++)
	{
		if (dp[i - 1] < n && a[dp[i - 1] + 1] == b[i])
		{
			dp[i] = dp[i - 1] + 1;
		}
		else
		{
			dp[i] = dp[i - 1];
		}
	}
	cout << dp[m] << endl;
	return;
}

Problem - C - Codeforces

思路：

令a[1]=x[1]+1后我们可以让a[i+1]=a[i]+x[i]，但是这样的话数可能会比较小，所以我们可以累加a[i]，因为是mod所以只要不大于x[i+1]可以一直加下去

代码：

void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
		cin >> x[i];
	a[1] = x[1] + 1;
	for (int i = 1; i < n; i++)
	{
		a[i + 1] = a[i] + x[i];
		while (a[i + 1] <= x[i + 1])
		{
			a[i + 1] += a[i];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return;
}

P1020 [NOIP1999 提高组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目的第一问其实就是让我们求最长不上升子序列，第二问就是求有多少段最长不上升序列

dp代码：

void solve2()
{
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		dp[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (a[j] > a[i])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		res = max(res, dp[i]);
	}
	cout << ans << endl;
	return;
}

然后我们发现就只会有50分，因为这个代码的时间复杂度达到了n^2,和题目的要求时间复杂度差距非常大，我们改善一下

void solve()
{
	vector<int>c;
	int ans = 0;
	while (cin >> a[num])
	{
		dp[num] = 1;
		for (int i = 0; i < num; i++)
		{
			if (a[num] <= a[i])
			dp[num] = max(dp[num], dp[i] + 1);
		}
		ans = max(ans, dp[num]);
		int flag = 0;
		for (int i = 0; i < c.size(); i++)
		{
			if (c[i] >= a[num])
			{
				flag = 1;
				c[i] = a[num];
				break;
			}
		}
		if (flag == 0)c.push_back(a[num]);
		num++;
	}
	cout << ans << endl;
	cout << c.size() << endl;
	return;
}

我们用一个 vector来存放最长不上升子序列，当前数若比vector的所有数小就进行覆盖，若大则加进vector,这样子操作的话vector的长度就会是我们所需子序列的个数，提交之后发现还是只有100，只能说这道题对时间复杂度卡的太死了，继续优化，这个时候可以根据Dilworth 定理进行推断：

狄尔沃斯定理亦称偏序集分解定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。

得到如下代码：

void solve1()
{
	int ta = 0, x, tb = 0;
	while (cin >> x)
	{
		int s = 0;
		for (int i = 0; i < ta; i++)
		{
			if (a[i] < x)
			{
				a[i] = x;
				s = 1;
				break;
			}
		}
		if (s == 0)a[ta++] = x;
		s = 0;
		for (int i = 0; i < tb; i++)
		{
			if (b[i] >= x)
			{
				b[i] = x;
				s = 1;
				break;
			}
		}
		if (s == 0)b[tb++] = x;
	}
	cout << ta << endl << tb << endl;
	return;
}