d

// 宽度大的伞的价格不一定比小的价格低
// 6  4     6   3
// f[i]: 覆盖前 i 头牛需要的花费
// f[i]: 1 - i 头用一把伞， a[i] - a[1]+1 的花费
//     ：f[j] + cost(j+1 , i)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
const int M = 1e6 + 10;
int x[N], c[M] ;
int f[N], n, m;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> x[i];
	sort(x + 1, x + 1 + n);
	for (int i = 1; i <= m; i++)
		cin >> c[i];
	// 宽度大的伞的价格不一定比小的价格低
	for (int i = m - 1; i >= 1; i--) {
		if (c[i] > c[i + 1])
			c[i] = c[i + 1];
	}
	memset(f, 0x3f, sizeof f);
	f[0] = 0;   // 初始化
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++)
			f[i] = min(f[i], f[j] + c[x[i] - x[j + 1] + 1]);
	}
	cout << f[n];
	return 0;
}

C

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, a[N];
int q[N], t;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	q[++t] = a[1];
	for (int i = 2; i <= n; i++) {
		if (a[i] > q[t])
			q[++t] = a[i];
		else {
			int id = lower_bound(q + 1, q + 1 + t, a[i])  - q;
			q[id] = a[i];
		}
	}
	cout << t;
	return 0;
}

C

// 单调递增， a[i+1] >a[i]
// 单调不减 ， a[i+1] >= a[i]
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, f[N];
int a[N];
int res;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		f[i] = 1; // 自己一个
		// 放在之前的数字的末尾
		for (int j = 1; j < i; j++) {
			if (a[i] > a[j])
				f[i] = max(f[i], f[j] + 1);
		}
		res = max(res, f[i]);
	}
	cout << res;
	return 0;
}

B

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;
#define int long long
int n, k, l[N], r[N];
int f[N];
int sum[N];

// 状态 ， 转移方程， 优化
signed main() {
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
		cin >> l[i] >> r[i];
	f[1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (i - r[j] - 1 >= 0)
				f[i] += sum[i - l[j]] - sum[i - r[j] - 1];
			else if (i - l[j] >= 0)
				f[i] += sum[i - l[j]];
			f[i] %= mod;
		}
		sum[i] = (sum[i - 1] + f[i]) % mod;
	}
	cout << f[n];
	return 0;
}






//for (int x = l[j] ; x <= r[j] ; x++) {
//	if (i >= x)
//		f[i] += f[i - x];
//	f[i] %= mod;
//}
////
//l[i] = 1, r[i] = 3
//
////  区间的左右端点：[i-r[j] , i - l[j]]
//// sum[i - l[j] ] - sum[i-r[j]-1]
//f[i - 3]  f[i - 2]  f[i - 1], 前缀和，求区间和 ，
//
//
//// 前缀和  ，  sum[i] = sum[i-1] +a[i]