前言： 这是笔者保证做过的且我自己认为很不错的 d p dp dp题集，难度对应 c o d e f o r c e s codeforces codeforces1800 ? 2300 1800-2300 1800?2300不等。点击题目有链接。
Fence Job（前缀和优化）
思路：
首先读完题可发现的是每个 h [ i ] h[i] h[i]都有个极长区间，也就是 h [ i ] h[i] h[i]只能在这个区间内出现，且作为该区间内的极小值。
看数据应该是 n 2 n^2 n2的 d p dp dp,考虑从什么状态入手。我们发现不同的操作可能会出现相同的结果序列，那么我们从操作完最后的序列入手。 d p [ i ] [ j ] dp[i][j] dp[i][j]表示操作前 i i i个数，且最后一个数以 a [ j ] a[j] a[j]结尾的合法序列有多少种。考虑转移：如果最后一个数以 a [ j ] a[j] a[j]结尾，那么前一个数只能以 x x x结尾且 x ≤ a [ j ] x\leq a[j] x≤a[j]。
这么 d p [ i ] [ j ] = ∑ x = 1 j d p [ i ? 1 ] [ x ] , a [ x ] ≤ a [ j ] dp[i][j]=\sum_{x=1}^{j}{dp[i-1][x]},a[x]\leq a[j] dp[i][j]=∑x=1j?dp[i?1][x],a[x]≤a[j].用前缀和优化转移即可。
code:
cin >> n;
for(int i = 1;
i <= n;
i++) cin >> a[i];
for(int i = 1;
i <= n;
i++) {
for(int j = i + 1;
j <= n + 1;
j++)
if(a[j] < a[i]) {
r[i] = j;
break;
}
for(int j = i - 1;
j >= 0;
j--)
if(a[j] < a[i]) {
l[i] = j;
break;
}
}
for(int i = 1;
i <= n;
i++) {
for(int j = 1;
j <= n;
j++) {
if(i == 1) {
if(l[j] < i && i < r[j])
dp[i][j] = 1;
} else {
if(l[j] < i && i < r[j]) {
dp[i][j] += sum[i - 1][j];
}
}
sum[i][j] = sum[i][j - 1] + dp[i][j];
}
}
mint ans = 0;
for(int i = 1;
i <= n;
i++) ans += dp[n][i];
cout << ans << '\n';
Yaroslav and Two Strings 线性dp 思路：
很裸的线性 d p dp dp啊，发现状态无非就那么几个：
f [ i ] [ 0 ] : 前 i 个数仅有 s [ j ] ≤ w [ j ] f[i][0]:前i个数仅有s[j]\leq w[j] f[i][0]:前i个数仅有s[j]≤w[j]
f [ i ] [ 1 ] : 前 i 个数有 s [ j ] < w [ j ] & & s [ j ] > w [ j ] f[i][1]:前i个数有s[j]
f [ i ] [ 2 ] : 前 i 个数仅有 w [ j ] ≤ s [ j ] f[i][2]:前i个数仅有w[j]\leq s[j] f[i][2]:前i个数仅有w[j]≤s[j]
f [ i ] [ 3 ] : 前 i 个数仅有 s [ j ] = w [ j ] f[i][3]:前i个数仅有s[j]=w[j] f[i][3]:前i个数仅有s[j]=w[j]
暴力转移即可
code:
mint f[N][4];
signed main() {
#ifdef JANGYI
freopen("input.in", "r", stdin);
freopen("out.out", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string s, w;
cin >> s >> w;
s = ' ' + s;
w = ' ' + w;
f[0][3] = 1;
for(int i = 1;
i <= n;
i++) {
if(s[i] == '?' && w[i] == '?') {
for(int x = 0;
x <= 9;
x++)
for(int y = 0;
y <= 9;
y++) {
if(x < y) {
f[i][0] += f[i - 1][0] + f[i - 1][3];
f[i][1] += f[i - 1][1] + f[i-1][2];
} else if(x > y) {
f[i][1] += f[i - 1][1] + f[i - 1][0];
f[i][2] += f[i - 1][2] + f[i - 1][3];
} else {
f[i][1] += f[i - 1][1];
f[i][2] += f[i - 1][2];
f[i][0] += f[i - 1][0];
f[i][3] += f[i - 1][3];
}
}
}
if(s[i] != '?' && w[i] != '?') {
int x = s[i] - '0', y = w[i] - '0';
if(x > y) {
f[i][0] = 0;
f[i][1] = f[i - 1][1] + f[i - 1][0];
f[i][2] = f[i - 1][2] + f[i - 1][3];
f[i][3] = 0;
} else if(x == y) {
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1];
f[i][2] = f[i - 1][2];
f[i][3] = f[i - 1][3];
} else {
f[i][0] = f[i - 1][0] + f[i - 1][3];
f[i][1] = f[i - 1][1] + f[i - 1][2];
f[i][2] = 0;
f[i][3] = 0;
}
}
if(s[i] != '?' && w[i] == '?') {
int x = s[i] - '0';
for(int y = 0;
y <= 9;
y++) {
if(x > y) {
f[i][1] += f[i - 1][1] + f[i - 1][0];
f[i][2] += f[i - 1][2] + f[i - 1][3];
} else if(x == y) {
f[i][0] += f[i - 1][0];
f[i][1] += f[i - 1][1];
f[i][2] += f[i - 1][2];
f[i][3] += f[i - 1][3];
} else {
f[i][0] += f[i - 1][0] + f[i - 1][3];
f[i][1] += f[i - 1][1] + f[i - 1][2];
}
}
}
if(s[i] == '?' && w[i] != '?') {
int y = w[i] - '0';
for(int x = 0;
x <= 9;
x++) {
if(x > y) {
f[i][1] += f[i - 1][1] + f[i - 1][0];
f[i][2] += f[i - 1][2] + f[i - 1][3];
} else if(x == y) {
f[i][0] += f[i - 1][0];
f[i][1] += f[i - 1][1];
f[i][2] += f[i - 1][2];
f[i][3] += f[i - 1][3];
} else {
f[i][0] += f[i - 1][0] + f[i - 1][3];
f[i][1] += f[i - 1][1] + f[i - 1][2];
}
}
}
if(s[i] != '?' && w[i] != '?') {
int x = s[i] - '0', y = w[i] - '0';
if(x > y) {
f[i][1] = f[i - 1][1] + f[i - 1][0];
f[i][2] = f[i - 1][2] + f[i - 1][3];
f[i][3] = 0;
} else if(x == y) {
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1];
f[i][2] = f[i - 1][2];
f[i][3] = f[i - 1][3];
} else {
f[i][0] = f[i - 1][0] + f[i - 1][3];
f[i][1] = f[i - 1][1] + f[i - 1][2];
f[i][2] = 0;
f[i][3] = 0;
}
}
// for(int j = 0;
j < 4;
j++) D(f[i][j])
}
cout << f[n][1];
#ifdef JANGYI
cerr << "================================" << endl;
cerr << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
/*
仅有：
f[i][0] : s[i] <= w[i];
f[i][1] : s[i] < w[i] & s[i] > w[i];
f[i][2] : s[i] >= w[i];
f[i][3] : s[i] == w[i];
*/
杭电多校第三场[Two Permutations]（(https://acm.hdu.edu.cn/showproblem.php?pid=7173)（哈希或者记忆化搜索dp） 题意：
给定两个全排列数组 P , Q P,Q P,Q,和一个空数组 R R R,每次从两个数组的首位数字挑一个加到 R R R后面，然后删除该数组。问：给定最后形成的 R R R,求有多少种方案可以构成。
解法一：
我们会发现一个数字会出现两次，那么我们记录每个数字在 R R R中第一次，第二次出现的位置。对于当前数字 p [ i ] p[i] p[i]，枚举数字 p [ i + 1 ] p[i+1] p[i+1]出现的位置，那么这两个位置中间就要放 Q Q Q的一段，用哈希判断是否和 R R R这一段子串完全匹配即可。
code:
typedef unsigned long long ULL;
typedef long long LL;
typedef pair pii;
template void inline read(T &x) {
int f = 1;
x = 0;
char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1;
s = getchar();
}
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N = 3e5 + 10, M = N * 2, mod1 = 998244353, mod2 = 1e9 + 7;
inline LL ksm(LL a, LL b, int mod){
LL ans = 1;
for(;
b;
b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
return ans;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
//----------------------------------------------------------------------------------------//
ULL fb[N], fc[N << 1], p[N << 1];
int n, a[N], b[N], c[N << 1];
int dp[N][2], pos[N][2];
inline ULL get(ULL f[], int l, int r) {
return f[r] - f[l - 1] * p[r - l + 1];
}
inline bool check(int lb, int rb, int lc, int rc) {
if(lb > rb) return 1;
if(lb < 1 || rb > n || lc < 1 || rc > n + n) return 0;
return get(fb, lb, rb) == get(fc, lc, rc);
}
inline void up(int &x, int y) {
x = x + y >= mod1 ? x + y - mod1 : x + y;
}
void solve() {
read(n);
for(int i = 1;
i <= n;
i++) read(a[i]);
for(int i = 1;
i <= n;
i++) read(b[i]);
for(int i = 1;
i <= n + n;
i++) read(c[i]);
for(int i = 1;
i <= n;
i++) for(int j = 0;
j < 2;
j++) dp[i][j] = 0;
for(int i = 1;
i <= n;
i++) pos[i][0] = pos[i][1] = 0;
for(int i = 1;
i <= n;
i++) fb[i] = fb[i - 1] * 233 + b[i];
for(int i = 1;
i <= n << 1;
i++) fc[i] = fc[i - 1] * 233 + c[i];
for(int i = 1;
i <= n << 1;
i++) {
if(!pos[c[i]][0]) pos[c[i]][0] = i;
else pos[c[i]][1] = i;
}
int Q = 1;
for(;
Q <= n;
Q++) if(!pos[Q][0] || !pos[Q][1]) break;
if(Q != n + 1) {
puts("0");
return;
}
for(int j = 0;
j < 2;
j++) {
int x = pos[a[1]][j];
if(check(1, x - 1, 1, x - 1)) dp[1][j] = 1;
}
for(int i = 1;
i < n;
i++) {
for(int j = 0;
j < 2;
j++) {
if(dp[i][j]) {
int x = pos[a[i]][j];
for(int k = 0;
k < 2;
k++) {
int y = pos[a[i + 1]][k];
if(y <= x) continue;
if(check(x - i + 1, y - i - 1, x + 1, y - 1))
up(dp[i + 1][k], dp[i][j]);
}
}
}
}
int ans = 0;
for(int j = 0;
j < 2;
j++)
if(dp[n][j]) {
int x = pos[a[n]][j];
if(check(x - n + 1, n, x + 1, n + n )) up(ans, dp[n][j]);
}
printf("%d\n", ans);
}
signed main() {
#ifdef JANGYI
freopen("input.in", "r", stdin);
freopen("out.out", "w", stdout);
auto now = clock();
#endif
// ios::sync_with_stdio(false);
// cin.tie(0);
p[0] = 1;
for(int i = 1;
i < N << 1;
i++) p[i] = p[i - 1] * 233;
int T = 1;
read(T);
while(T--) {
solve();
}#ifdef JANGYI
cout << "================================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
} 解法二：
我们定义 d p [ i ] [ 0 / 1 ] dp[i][0/1] dp[i][0/1]表示 R R R的第 i i i位与 P / Q P/Q P/Q匹配的方案数。采用记忆化搜索的方法实现即可。
code：
int dp[2 * MAXN][2];
int dfs(int x, int y,int tar) {
if (x > n && y > n)return 1;
if (dp[x + y - 1][tar]!=-1)return dp[x + y - 1][tar];
int ans = 0;
if (P[x] == S[x + y - 1] && x <= n) {
ans += dfs(x + 1, y, 0);
ans %= mod;
}
if (Q[y] == S[x + y - 1] && y <= n) {
ans += dfs(x, y + 1, 1);
ans %= mod;
}
return dp[x + y - 1][tar] = ans;
}void slove() {
cin >> n;
for (int i = 0;
i <= 2 * n + 5;
i++)dp[i][0] = dp[i][1] = -1;
for (int i = 1;
i <= n;
i++)cin >> P[i];
for (int i = 1;
i <= n;
i++)cin >> Q[i];
for (int i = 1;
i <= 2 * n;
i++)cin >> S[i];
int ans = 0;
if (P[1] == S[1])ans += dfs(2, 1, 0), ans %= mod;
if (Q[1] == S[1])ans += dfs(1, 2, 1), ans %= mod;
cout << ans << endl;
}
杭电多校第二场：E Slayers Come（线段树并查集优化） 题意：
给定一个长度为 n n n的数组，每个位置有一个怪兽，有血量 b [ i ] b[i] b[i]和攻击力 a [ i ] a[i] a[i]。有 m m m个技能，每个技能有三个参数： V , L , R V,L,R V,L,R：可以杀死 V V V位置的怪物，这个怪物死后会攻击两边的怪，对左边造成 a [ i ] ? L a[i]-L a[i]?L伤害，右边造成 a [ i ] ? R a[i]-R a[i]?R的伤害。求如何组合技能使每个怪都被至少杀一次的方案。
思路：
首先可以发现每个技能是可以杀死一段区间内的怪物，那么我们如果能处理出来所有技能的区间 [ L , R ] [L,R] [L,R]，那么问题就转化为从这些技能中选取若干使得区间 [ 1 , n ] [1,n] [1,n]被覆盖，就是区间完全覆盖问题，看数据范围，很容易想到线段树优化，经典题啊！那么我们就该考虑如何快速求出每个技能的区间。依题意如果 a [ i ] ? r [ k ] ≥ b [ i + 1 ] a[i]-r[k] \geq b[i+1] a[i]?r[k]≥b[i+1]，那么我们就可以通过传递杀死它，那么我们把 a [ i ] ? b [ i + 1 ] a[i]-b[i+1] a[i]?b[i+1]按从大到小排序，把每个技能的 r r r从小到大排序，优先处理容易死的怪，如果满足上述关系，那么就把 [ i , i + 1 ] [i,i+1] [i,i+1]合并到一个连通块里，用并查集优化。左端点同理。
那么接下来解决如何组合技能是区间被重复覆盖。
对于当前区间 [ L , R ] [L,R] [L,R],
d p [ r ] + = ∑ j = L ? 1 R d p [ j ] dp[r]+=\sum_{j=L-1}^{R}{dp[j]} dp[r]+=∑j=L?1R?dp[j] ：选这个区间，那么左端点接在 [ L ? 1 , R ] [L-1,R] [L?1,R]的位置，都可以使 [ 1 , R ] [1,R] [1,R]被覆盖。
0 ≤ j ≤ L ? 2 , d p [ j ] = d p [ j ] ? 2 0\leq j \leq L-2,dp[j] =dp[j]*2 0≤j≤L?2,dp[j]=dp[j]?2：选不选这个区间，区间 [ 0 , L ? 2 ] [0,L-2] [0,L?2]还是会被覆盖，因为题目问的是如何组合技能。
优化用线段树即可。
code:
来自大佬的代码
#include
#include
#include using namespace std;
#define int long long
typedef pair PII;
const int N = 2e5 + 10, mod = 998244353;
int n, m, a[N], b[N];
struct Node
{
int v, l, r;
int ll, rr;
}sk[N];
struct Tree
{
int l, r;
int sum;
int tag;
}tr[N << 2];
int p[N];
PII d[N];
int find(int x)// 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}void pushup(int u)
{
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if(root.tag > 1)
{
left.sum = left.sum * root.tag % mod, right.sum = right.sum * root.tag % mod;
left.tag = left.tag * root.tag % mod, right.tag = right.tag * root.tag % mod;
root.tag = 1;
}
}void build(int u, int l, int r)
{
tr[u] = {l, r, 0, 1};
if(l == r) return ;
else
{
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}void add(int u, int x, int v)
{
if(x == tr[u].l && x == tr[u].r) tr[u].sum = (tr[u].sum + v) % mod;
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) add(u << 1, x, v);
if(x > mid) add(u << 1 | 1, x, v);
pushup(u);
}
}void mul(int u, int l, int r)
{
if(l <= tr[u].l && r >= tr[u].r)
{
tr[u].sum = tr[u].sum * 2 % mod;
tr[u].tag = tr[u].tag * 2 % mod;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) mul(u << 1, l, r);
if(r > mid) mul(u << 1 | 1, l, r);
pushup(u);
}
}int query(int u, int l, int r)
{
if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid) res = (res + query(u << 1, l, r)) % mod;
if(r > mid) res = (res + query(u << 1 | 1, l, r)) % mod;
pushup(u);
return res % mod;
}
}void solve()
{
cin >> n >> m;
for(int i = 1 ;
i <= n ;
i ++ ) cin >> a[i] >> b[i];
for(int i = 1 ;
i <= m ;
i ++ )
{
int v, l, r;
cin >> v >> l >> r;
sk[i] = {v, l, r};
}
for(int i = 1 ;
i <= n ;
i ++ ) p[i] = i;
for(int i = 1 ;
i < n ;
i ++ ) d[i] = {a[i] - b[i + 1], i};
sort(d + 1, d + n);
sort(sk + 1, sk + m + 1, [](Node &a, Node &b){
return a.r > b.r;
});
int cur = n - 1;
for(int i = 1 ;
i <= m ;
i ++ )
{
while(cur >= 1 && d[cur].first >= sk[i].r)
{
int pos = d[cur].second;
p[pos] = pos + 1;
cur -- ;
}
sk[i].rr = find(sk[i].v);
}for(int i = 1 ;
i <= n ;
i ++ ) p[i] = i;
for(int i = 1 ;
i < n ;
i ++ ) d[i] = {a[i + 1] - b[i] , i};
sort(d + 1, d + n);
sort(sk + 1, sk + m + 1, [](Node &a, Node &b){
return a.l > b.l;
});
cur = n - 1;
for(int i = 1 ;
i <= m ;
i ++ )
{
while(cur >= 1 && d[cur].first >= sk[i].l)
{
int pos = d[cur].second;
p[pos + 1] = pos;
cur --;
}
sk[i].ll = find(sk[i].v);
}
sort(sk + 1, sk + m + 1, [](Node &a, Node &b){
return a.rr < b.rr;
});
build(1, 0, n);
add(1, 0, 1);
for(int i = 1 ;
i <= m ;
i ++ )
{
int l = sk[i].ll , r = sk[i].rr;
add(1, r, query(1, l - 1, r));
if(l >= 2) mul(1, 0, l - 2);
}
cout << query(1, n, n) << endl;
}signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int T = 1;
cin >> T;
while(T -- ) solve();
return 0;
}
Pawn（背包+记录路径） 思路：
【dp|最近写过的dp题单（持续更新）】首先 f [ i ] [ j ] [ w ] f[i][j][w] f[i][j][w]表示从底部走到 ( i , j ) (i,j) (i,j)且当前所有豆子总数 m o d ( k + 1 ) = w mod(k+1)=w mod(k+1)=w的最大豆子数。
那么转移我们就直接枚举是从下一层哪个方向走过来的即可，顺便记录一下路径。
code:
template
struct modint {
unsigned int x;
constexpr modint()noexcept:x(){}
template
constexpr modint(T x_)noexcept:x((x_%=m)<0?x_+m:x_){}
constexpr unsigned int val()const noexcept{return x;
}
constexpr modint&operator++()noexcept{if(++x==m)x=0;
return*this;
}
constexpr modint&operator--()noexcept{if(x==0)x=m;
--x;
return*this;
}
constexpr modint operator++(int)noexcept{modint res=*this;
++*this;
return res;
}
constexpr modint operator--(int)noexcept{modint res=*this;
--*this;
return res;
}
constexpr modint&operator+=(const modint&a)noexcept{x+=a.x;
if(x>=m)x-=m;
return*this;
}
constexpr modint&operator-=(const modint&a)noexcept{if(x>=1)if(n&1)r*=x;
return r;
}
constexpr modint inv()const noexcept {
int s=x,t=m,x=1,u=0;
while(t)
{
int k=s/t;
s-=k*t;
swap(s,t);
x-=k*u;
swap(x,u);
}
return modint(x);
}
friend constexpr modint operator+(const modint&a,const modint&b){return modint(a)+=b;
}
friend constexpr modint operator-(const modint&a,const modint&b){return modint(a)-=b;
}
friend constexpr modint operator*(const modint&a,const modint&b){return modint(a)*=b;
}
friend constexpr modint operator/(const modint&a,const modint&b){return modint(a)/=b;
}
friend constexpr bool operator==(const modint&a,const modint&b){return a.x==b.x;
}
friend constexpr bool operator!=(const modint&a,const modint&b){return a.x!=b.x;
}
friend ostream&operator<<(ostream&os,const modint&a){return os<>(istream&is,modint&a){long long v;
is>>v;
a=modint(v);
return is;
}
};
using mint = modint<1000000007>;
// using mint = modint<998244353>;
namespace Combine{
const int Combine_max = 1e5 + 50;
mint fac[Combine_max];
void init() { fac[0] = 1;
for (int i = 1;
i < Combine_max;
++ i) fac[i] = fac[i - 1] * i;
}
mint A(int n, int m) { return fac[n] / fac[n - m];
}
mint C(int n, int m) { return fac[n] / (fac[n - m] * fac[m]);
}
mint ksm(mint x, int exp){
mint res = 1;
for (;
exp;
x *= x, exp >>= 1) if (exp & 1) res *= x;
return res;
}
}
using namespace Combine;
int f[111][111][11];
//f[i][j][w]走到(i,j)，价值mod(k+1)=w的最大价值
int n, m, a[111][111];
pii road[111][111][11];
signed main() {
#ifdef JANGYI
freopen("input.in", "r", stdin);
freopen("out.out", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> n >> m >> k;
k++;
memset(f, -1, sizeof f);
for(int i = 1;
i <= n;
i++) {
string s;
cin >> s;
for(int j = 1;
j <= m;
j++)
a[i][j] = s[j - 1] - '0';
}
for(int i = n;
i >= 1;
i--) {
for(int j = 1;
j <= m;
j++) {
if(i == n) f[n][j][a[i][j] % k] = a[i][j];
else {
for(int w = 0;
w < k;
w++) {
if(j > 1 && f[i + 1][j - 1][(w - a[i][j] % k + k) % k] != -1 && f[i + 1][j - 1][(w - a[i][j] % k + k) % k] + a[i][j] > f[i][j][w]) {
f[i][j][w] = f[i + 1][j - 1][(w - a[i][j] % k + k) % k] + a[i][j];
road[i][j][w] = {j - 1, (w - a[i][j] % k + k) % k};
}
if(j < m && f[i + 1][j + 1][(w - a[i][j] % k + k) % k] != -1 && f[i + 1][j + 1][(w - a[i][j] % k + k) % k] + a[i][j] > f[i][j][w]) {
f[i][j][w] = f[i + 1][j + 1][(w - a[i][j] % k + k) % k] + a[i][j];
road[i][j][w] = {j + 1, (w - a[i][j] % k + k) % k};
}
}
}
}
}
int ans = -1, id;
for(int i = 1;
i <= m;
i++) {
if(f[1][i][0] > ans) {
ans = f[1][i][0];
id = i;
}
}
// D(id)
if(ans == -1) {
cout << -1 << '\n';
return 0;
}
cout << ans << '\n';
int i = 1, j = id, w = 0;
vector> pos;
while(i != n) {
pii now = road[i][j][w];
if(now.fi == j - 1) pos.pb("R");
else pos.pb("L");
// DD(i, j)
i++;
j = now.fi;
w = now.se;
}
cout << j << '\n';
reverse(all(pos));
for(auto t : pos) cout << t;
#ifdef JANGYI
cerr << "================================" << endl;
cerr << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
推荐阅读
- 聚类|机器学习-常见聚类算法K-means，模糊c-均值，谱聚类 DBSCAN算法等
- 深入浅出讲解自然语言处理|【聚类】详解常用的聚类算法（K-Means、DBSCAN等）
- FDTD学习笔记|Lumerical官方案例、FDTD时域有限差分法仿真学习（三）——环形谐振器(Ring resonator)之第一部分
- FDTD学习笔记|Lumerical官方案例、FDTD时域有限差分法仿真学习（六）——等离子体超材料吸收器（Plasmonic metamaterial absorber）
- FDTD学习笔记|Lumerical官方案例、FDTD时域有限差分法仿真学习（二）——宽带光栅耦合器(Broadband grating coupler (2D))
- 卷积|何恺明团队新作（只用普通ViT，不做分层设计也能搞定目标检测）
- 数据结构|递归算法简介
- 数据结构|面对对象编程细则（三）
- 数据结构|浅谈算法分析