数据有点鬼畜

题目一

试题名称：游戏

【题面描述】

你有四个正整数 n,a,b,c，并准备用它们玩一个简单的小游戏。

在一轮游戏操作中，你可以选择将 n 减去 a，或是将 n 减去 b。
游戏将会进行多轮操作，直到当 n≤c 时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将 n 减去 a，而另一种操作序列选择将 n 减去 b。
如果 a=b，也认为将 n 减去 a 与将 n 减去 b 是不同的操作。

由于答案可能很大，你只需要求出答案对 1,000,000,007 取模的结果。

【输入格式】

一行四个正整数 n,a,b,c。
保证 1≤a,b,c≤n。

【输出格式】
一行一个整数，表示不同的游戏操作序列数量对 1,000,000,007 取模的结果。

【样例1】
1 1 1 1
1
【样例2】
114 51 4 1
176
【样例3】
114514 191 9 810
384178446

【数据范围】

对于 20% 的测试点，保证 a=b=c=1，n≤30。

对于 40% 的测试点，保证 c=1，n≤103。
对于所有测试点，保证 1≤n≤2×10^5。

这道题你可以先写一个暴力我用的是记忆化搜索,官方给的代码好像直接是一个线性dp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = 1000000007;
ll n, a, b, c;

ll dfs(ll u)
{
	if (u <= c) return 1;
	
	return (dfs(u - a) % mod + dfs(u - b) % mod) % mod;
}

int main()
{
	ios::sync_with_stdio(false);	
	cin.tie(0);
	
	cin >> n >> a >> b >> c;

	cout << dfs(n);
	
	
	return 0;
}

然后你就直接加一个记忆化搜索就完啦 QWQ

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = 1000000007;
ll n, a, b, c;
ll cnt;
map<ll, ll> f;

ll dfs(ll u)
{
	if (f[u]) return f[u];
	
	if (u <= c) return 1;

	return f[u] = (dfs(u - a) % mod + dfs(u - b) % mod) % mod;
}

int main()
{
	ios::sync_with_stdio(false);	
	cin.tie(0);
	
	cin >> n >> a >> b >> c;

	cout << dfs(n);
	
	
	return 0;
}

题目二

【问题描述】

你有 10^9 个牛棚，从左到右一字排开。你希望把 N 头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。
其中，第 i 头牛的攻击范围是 (ai,bi)，这意味着，如果他的左边 ai 个牛棚或右边 bi 个牛棚里有其他牛，他就会去挑事。

你想留下连续的一段牛棚，并把其他牛棚都卖掉。请问你最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的 N 头牛都安置进剩余的牛棚里，且没有牛会挑事？

【输入描述】

第一行 1 个正整数 N。

接下来一行 N 个用空格隔开的正整数 a1,…,aN。

接下来一行 N 个用空格隔开的正整数 b1,…,bN。

【输出描述】

输出一行一个整数，表示你最少需要留下多少牛棚。

【特别提醒】

在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。

【样例输入 1】

2
1 2
1 2
【样例输出 1】

4
【样例解释 1】

你可以留下 4 个牛棚，并如此安排你的牛：

牛棚 1    牛棚 2   牛棚 3     牛棚 4
 牛 1         *          *            牛 2

【样例输入 2】

3
1 2 3
3 2 1
【样例输出 2】

7
【数据规模】

对于 20% 的测试点，保证 N=2；
对于另外 20% 的测试点，保证 N=3；
对于 80% 的测试点，保证 N≤8；对于所有测试点，保证 N≤9，ai,bi≤1000。

这道题的话也很简单, 先写一个给出当前序列所需要的最小牛棚 由于数据很小 直接枚举一遍就完啦

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 10;
PII g[N];
map<int, int> st;

int main()
{
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++) cin >> g[i].first;
	for (int i = 0; i < n; i++) cin >> g[i].second;
	
	int ans = 1e9;
	do
	{
		int res = 1, k = g[0].second;
		for (int i = 1; i < n; i++)
		{
			res += max(k, g[i].first) + 1;
			k = g[i].second;
		}
		
		ans = min(ans, res);
	}
	while(next_permutation(g, g + n));

	cout << ans;
	
	
	return 0;
}

注:并非题解

看在作者这么努力的情况下 给他一个赞❤️吧 QWQ