这周继续刷dp
10.19 周一
P4017 最大食物链计数
记忆化搜索就完事
在笔纸上模拟一下就很容易想出来
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 5e3 + 10;
const int MOD = 80112002;
vector<int> g[MAXN];
int f[MAXN], out[MAXN], in[MAXN], n, m, ans;int dfs(int v)
{if(f[v]) return f[v];int res = 0;REP(i, 0, g[v].size())res = (res + dfs(g[v][i])) % MOD;return f[v] = res;
}int main()
{scanf("%d%d", &n, &m);while(m--){int u, v;scanf("%d%d", &u, &v);g[v].push_back(u);in[v] = out[u] = 1;}_for(i, 1, n) if(!in[i]) f[i] = 1;_for(i, 1, n) if(!out[i]) ans = (ans + dfs(i)) % MOD;printf("%d\n", ans);return 0;
}
P1020 导弹拦截
复习最长不下降子序列写法，学会二分cmp
上升lower 不下降upper
用到一个神奇的定理（不会证）
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
int a[MAXN], d[MAXN], len, n;bool cmp(int a, int b)
{return a > b;
}int main()
{while(~scanf("%d", &a[++n])); n--;d[1] = a[1]; len = 1;_for(i, 2, n){if(a[i] <= d[len]) d[++len] = a[i];else d[upper_bound(d + 1, d + len + 1, a[i], cmp) - d] = a[i]; } printf("%d\n", len);d[1] = a[1]; len = 1;_for(i, 2, n){if(a[i] > d[len]) d[++len] = a[i];else d[lower_bound(d + 1, d + len + 1, a[i]) - d] = a[i]; } printf("%d\n", len);return 0;
}
P1091 合唱队形
有点水
其实是利用了n方那个做法的数组
所以说学算法的时候最好不要死记硬背，这里就考到了数组的意义
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 110;
int a[MAXN], f1[MAXN], f2[MAXN], n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]), f1[i] = f2[i] = 1;_for(i, 1, n)_for(j, 1, i - 1)if(a[i] > a[j])f1[i] = max(f1[i], f1[j] + 1);for(int i = n; i >= 1; i--)for(int j = n; j > i; j--)if(a[i] > a[j])f2[i] = max(f2[i], f2[j] + 1);int ans = 0;_for(i, 1, n) ans = max(ans, f1[i] + f2[i] - 1);printf("%d\n", n - ans);return 0;
}
时刻注意一个原则
独立思考，不抄题解
10.20 周二
P1233 木棍加工
这题是导弹拦截的拓展题
只是一开始要先排序，以及比较的方式变了一下
我写了三种做法
n方不用定理
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 5e3 + 10;
struct node
{int l, w;
}a[MAXN];
int f[MAXN], vis[MAXN], n, ans;bool cmp(node x, node y)
{return (x.l > y.l) || (x.l == y.l && x.w > y.w);
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &a[i].l, &a[i].w);sort(a + 1, a + n + 1, cmp);int ans = 0;_for(i, 1, n)if(!vis[i]){ans++;int p = i;_for(j, i + 1, n)if(!vis[j] && a[p].l >= a[j].l && a[p].w >= a[j].w)vis[j] = 1, p = j;}printf("%d\n", ans);return 0;
}n方用定理 注意n方做法一定要初始化（定理的话与原来反向就行）
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 5e3 + 10;
struct node
{int l, w;
}a[MAXN];
int f[MAXN], n, ans;bool cmp(node x, node y)
{return (x.l > y.l) || (x.l == y.l && x.w > y.w);
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &a[i].l, &a[i].w);sort(a + 1, a + n + 1, cmp);ans = 1;_for(i, 1, n){f[i] = 1; //初始化!! _for(j, 1, i - 1) if(!(a[j].l >= a[i].l && a[j].w >= a[i].w)) {f[i] = max(f[i], f[j] + 1);ans = max(ans, f[i]);}}printf("%d\n", ans);return 0;
}nlogn做法
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 5e3 + 10;
struct node
{int l, w;
}a[MAXN], d[MAXN];
int f[MAXN], len, n;bool cmp1(node x, node y)
{return (x.l > y.l) || (x.l == y.l && x.w > y.w);
}bool cmp2(node x, node y)
{return !(x.l >= y.l && x.w >= y.w);
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &a[i].l, &a[i].w);sort(a + 1, a + n + 1, cmp1);d[1] = a[1]; len = 1;_for(i, 2, n){if(cmp2(d[len], a[i])) d[++len] = a[i];else d[lower_bound(d + 1, d + len + 1, a[i], cmp2) - d] = a[i];}printf("%d\n", len);return 0;
}
10.24 周六
这周社团活动开始多起来了，有点不适应，所以这周训练少了点
下周把握好节奏，训练量会回来
我全都要
P2758 编辑距离
这道dp题终于又独立相出
我一直忘记初始化了
写dp三件事很重要
设计状态，写转移方程，初始化
这里我直接忘记初始化了
这个发现没有初始化的问题是我试了一下简单样例发现的
所以有时候卡住的时候可以试下简单案例，要学会这个方法
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 2e3 + 10;
char a[MAXN], b[MAXN];
int f[MAXN][MAXN];int main()
{scanf("%s%s", a + 1, b + 1);int lena = strlen(a + 1), lenb = strlen(b + 1);_for(i, 1, lena) f[i][0] = i;_for(i, 1, lenb) f[0][i] = i;_for(i, 1, lena)_for(j, 1, lenb){f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1;if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i-1][j-1]);}printf("%d\n", f[lena][lenb]);return 0;
}