文章目录
The Third Week
战略上藐视敌人，战术上重视敌人 ———— 毛泽东主席
一、前言
周六打了场cf，只过了俩题而且比较慢，给我的id上个颜色怎么这么费事呢。链接: link
周一队内训练赛，ac俩题速度还行，但是有不少人ac四题，dfs和dp的应用都没有想到，后来都补出来了。链接: link
周二晚上有一场cf，没打，周三早上打的，div2 ac俩题。还没补题。
周三下午河南萌新联赛，签到题特别签到，算法题特别算法，打得不是特别好，速度还行。补题也非常费劲，算法补的我眼花缭乱了已经。链接: link
周五早上队内训练赛，打的非常不好，很多思维题的思路都需要很长时间才能想出来，更尴尬的是在结束后几秒a了一道题，这要是在赛场上得气死，但是思维题也不知道该怎么才能快点想出来。链接: link
周六早上队内训练赛，不想说了已经。补题了还没写题解。
二、算法
1.KMP算法
adbq学了但是不会用，等过俩天再来补这个算法
2.线性DP
问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的策略必须是基于当前状态（由上一次决策产生）的最优决策。（异或，除余都不适用常规动态规划）
- 结合原问题和子问题确定状态：
（1）描述位置的：前（后）i单位，第i到第j单位，坐标为（i，j）第i个之前（后）且必须取第i个等
（2）描述数量的：取i个，不超过i个，至少i个等
（3）描述对后有影响的：状态压缩的，一些特殊的性质 - 确定转移方程：
（1）检查参数是否足够
（2）分情况：最后一次操作的方式，取不取，怎么样取
（3）初始边界是什么
（4）注意无后效性。（比如说，求A求要求B，求B就要求C，求C就要求A，这就不符合无后效性。） - 需不需要优化
- 确定编程实现方式
（1）递推
（2）记忆化搜索
<1>（最长上升子序列 II）
题解：
相比较I，II的数据增大了100倍，所以无法直接采用o(n * n)的算法，而是用了一种o(n * log(n))的算法，贪心➕二分。
数组q[i]储存长度为i的序列的最小的结尾元素，最终输出q的长度即可。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#include<utility>
using namespace std;
#define int long long
const int N = 1e5+10;
int n;
int a[N],q[N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int res = 0;
q[++res] = a[1];
//可以简单看出q数组是递增的
for (int i = 2; i <= n; i++) {
if(a[i] > q[res])q[++res] = a[i];
//如果比末尾值大，继续加入即可
else {
int l = 1,r = res;
while(l < r) {
//二分
int mid = (l+r)/2;
if(q[mid] < a[i])l = mid+1;
else r = mid;
}
//找出第一个大于等于a[i]的值
//把那个位置的q[r]变成a[i]
q[r] = a[i];}
}
cout << res << endl;
return 0;
}
3.背包DP
- 01背包
给定n件重量为w，价值为v的物品，问一个可承载m重量的背包最多能获得多少价值，是每件东西的取存问题，所以是01背包
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if(j < w[i]) dp[i][j] = dp[i-1][j]; //放不下这件物品
else dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
//选取放和不放之间的较优态
}
}
- 完全背包
还是n类重量为w，价值为v的物品，这次每个物品可以无限次的取
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i-1][j];
//考虑一下要不要放啦
if(j >= w[i])dp[i][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
//直接在当前的第i个物品处考虑需不需要往下继续放
}
}