阅读量:0
思路：
这其实是一道数学题（最开始一直在枚举，服啦）
我们的目的是求最大利润
当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来出售
还可以参考我觉得挺好的一篇题解：
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; }
思路：
采用双指针，一个指向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; }还有一篇动态规划的题解我感觉也不错
代码奉上：
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; }
思路：
令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; }