「NOIP Record」#8 搜索剪枝与记忆化搜索
|
Record
|

3677 字
|
54 分钟

搜索剪枝

纯搜索剪枝题很少，早就融入各种搜索之中了。

但是在各种多项式时间的搜索里，剪枝仍然是重要的。

目前只有一道题，以后看情况加。

luogu1120 小木棍

能注意到长度一定是所有木棍总和的倍数，并且至少是 $\max{a_i}$，所以只对这部分搜索就行。

设dfs(cnt,len,lst)表示当前还剩下 $cnt$ 根木棍要拼接，当前木棍剩余长度为 $len$ ，使用的上一根木棍长度为 $lst$ 的情况下，能否搜到答案。

枚举每根木棍选不选的复杂度过高，但是也没有其他好办法，所以尝试剪枝。

  1. 如果使用长度为 $a_i$ 的木棍搜不到答案，那么直接尝试另一种长度。
  2. 长度小的木棍更灵活，产生的状态数必然更多，也更容易在剩余长度小时找到答案，所以改变搜索顺序，优先搜索长度大的。
  3. 如果当前使用的木棍长度等于 $len$ 且仍然搜不到答案，那么直接返回无解。

这样就来到了一个玄学复杂度，能够通过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define psb push_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=70;
int n, len, s, a[N], c[N], pre[N];
bool dfs(int cnt,int le,int st) {
    if(le==0) { return dfs(cnt-1,len,a[n]); }
    if(cnt==0) return 1;
    st=min(st,le);
      // 长度不能大于le
    while(st&&!c[st]) --st;
    while(st) {
        if(c[st]) {
            --c[st];
            int fg=dfs(cnt,le-st,st);
            ++c[st];
            if(((le==st)||(le==len))&&!fg) return 0;
            // 3
            else if(fg) return 1;
            st=pre[st];
            // 1
        } else st=pre[st];
    }
    return 0;
}
signed main() {
    n=read();
    rep(i,1,n) a[i]=read(), ++c[a[i]], s+=a[i];
    sort(a+1,a+n+1); // 2
    rep(i,1,n) if(a[i]!=a[i-1]) pre[a[i]]=a[i-1];
    for(len=a[n];2*len<=s;++len) if(s%len==0) {
        if(dfs(s/len,len,a[n])) { printf("%lld\n",len); exit(0); }
    }
    printf("%lld\n",s);
}

记忆化搜索

重点，适合用来打部分分。

用来转移状压 DP 也是好的，可以剪掉很多废状态。

记忆化搜索分为两种。

  1. 用 DP 的思想，记录自底向上某个状态的最优解或方案数。这样做就相当于用搜索实现 DP，具有 DP 的那些性质，遇到一个已经访问过的状态便可以直接返回。
  2. 更接近于对一般搜索的优化，记录到从初始状态到达当前状态的搜索树上的边权和，这样只有当再次搜到这个状态时，当前边权和劣于记录的值，才能直接返回，否则就要更新记录的边权和。效率一般低于前者，且对搜索顺序要求较高。

很多时候都是二者皆可用的，那为啥后者还存在呢？

用 DP 的理论，前者要求记录的状态满足最优子结构性质，后者则只是提取出最优子结构一个子集。一般使用前者。

第 2 种看起来挺没用的，不过它放宽了太多条件，根本不必考虑最优性，直接暴搜就行，在某些时候有奇效，比如可以应用搜索顺序优化。

luogu3609 [USACO17JAN] Hoof, Paper, Scissor G

要把整个序列划分成至多 $k$ 段，考虑到 $k$ 不大，$O(nk)$ 的 DP 是容易做的。

设 $f(i,k,cur)$ 表示当前在 $i$，分了 $k$ 段，手势是 $cur$ 的最大值。

要么接在后面，要么新开一段。

这个满足最优子结构性质，可以使用第 1 种方法。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=1e5+5;
int n, k, ans, s[N];
int f[N][22][3];
int winwin(int x,int y) {
    if(x==0&&y==1) return 1;
    if(x==1&&y==2) return 1;
    if(x==2&&y==0) return 1;
    return 0;
}
int dfs(int i,int k,int cur) {
    if(i==0) return 0;
    if(f[i][k][cur]) return f[i][k][cur];
    int& res=f[i][k][cur];
    res=dfs(i-1,k,cur)+winwin(cur,s[i]);
    if(k) {
        rep(j,0,2) if(cur!=j) res=max(res,dfs(i-1,k-1,j)+winwin(cur,s[i]));
    }
    return res;
}
signed main() {
    n=read(), k=read();
    rep(i,1,n) {
        char c; scanf(" %c",&c);
        if(c=='H') s[i]=0;
        else if(c=='S') s[i]=1;
        else if(c=='P') s[i]=2;
    }
    rep(i,0,k) rep(j,0,2) ans=max(ans,dfs(n,i,j));
    printf("%lld\n",ans);
}

luogu1278 单词游戏

$n$ 很小，考虑状压 $n$。

设 $f(S,pre)$ 为选了集合 $S$ 中的串，上一个选的串是 $pre$ 的最大值。

然后就做完了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define psb push_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=20;
int n, ans, f[(1<<17)+5][N];
string s[N];
int dfs(int S,int pre) {
    if(f[S][pre]) return f[S][pre];
    int& res=f[S][pre];
    rep(i,0,n-1) if((S&(1<<i))==0) {
        int l=s[pre].size()-1;
        if(!pre||s[pre][l]==s[i+1][0]) {
            res=max(res,dfs(S|(1<<i),i+1)+(int)s[i+1].size());
        }
    }
    return res;
}
signed main() {
    n=read();
    s[0]=" ";
    rep(i,1,n) cin>>s[i];
    printf("%lld\n",dfs(0,0));
}

luogu2476 [SCOI2008] 着色方案

注意到颜色只有 $5$ 种，用典题乌龟棋的做法，记录上一个放的什么颜色即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define psb push_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=16, mod=1e9+7;
int k, t[N], f[N][N][N][N][N][6];
int dfs(int a,int b,int c,int d,int e,int lst) {
    if(~f[a][b][c][d][e][lst]) return f[a][b][c][d][e][lst];
    int& res=f[a][b][c][d][e][lst];
    res=0;
    if(a+b+c+d+e==0) return res=1;
    if(a) (res+=(a-(lst==2))*dfs(a-1,b,c,d,e,1)%mod)%=mod;
    if(b) (res+=(b-(lst==3))*dfs(a+1,b-1,c,d,e,2)%mod)%=mod;
    if(c) (res+=(c-(lst==4))*dfs(a,b+1,c-1,d,e,3)%mod)%=mod;
    if(d) (res+=(d-(lst==5))*dfs(a,b,c+1,d-1,e,4)%mod)%=mod;
    if(e) (res+=e*dfs(a,b,c,d+1,e-1,5)%mod)%=mod;
    return res;
}
signed main() {
    k=read();
    rep(i,1,k) ++t[read()];
    SET(f,-1);
    printf("%lld\n",dfs(t[1],t[2],t[3],t[4],t[5],0));
}

另外的，本题相当于是 CF840C 的弱化弱化版。

luogu8565 Sultan Rage

题目乍一看很可怕。

然而能发现 $\text{Fibonacii}$ 序列应该是题目中序列的一个极小情况，但增长已经是指数级了。也就是说给出的序列在超过 $m$ 的部分里，有用的最多六十多项。

考虑记忆化搜索，设 $f(k,x)$ 为用前 $k$ 项凑成 $x$ 的方案数，转移就是背包。

$x$ 这一维很大，但 $m$ 位之后能搞一个进位操作，直觉上数量不是很多，所以可以用std::unordered_map实现。对于前 $m$ 项直接用背包处理答案，这部分状态数不会太少。

可以做一些优化。

  1. 如果 $x> \sum_{i=1}^k a_i$，那么直接返回 $0$。
  2. 如果 $x \le \sum_{i=1}^k a_i$ 并且 $x > \sum_{i=1}^{k-1} a_i$，那么 $a_k$ 就必须选择。

复杂度 $\text{proof by AC}$。

可以就此了解一下 $\text{Zeckendorf ’s theorem}$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define psb push_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=233, mod=998244353;
int T, n, m, q, a[N], s[N], f[N*100];
unordered_map<int,int> g[N];
int dfs(int x,int k) {
    if(x<0||x>s[k]) return 0;
    if(x==0) return 1;
    if(g[k].count(x)) return g[k][x];
    if(k==n) return g[k][x]=f[x];
    if(x>s[k-1]) g[k][x]=dfs(x-a[k],k-1);
    return g[k][x]=(dfs(x-a[k],k-1)+dfs(x,k-1))%mod;
}
void solve() {
    n=read(), q=read();
    rep(i,1,n) a[i]=read(), s[i]=s[i-1]+a[i], g[i].clear();
    memset(f,0,(s[n]+1)<<3);
    f[0]=1;
    rep(i,1,n) per(j,s[i],a[i]) {
        if(j>=a[i]) (f[j]+=f[j-a[i]])%=mod;
    }
    m=n+1;
    for(;;++m) {
        a[m]=0;
        for(int i=1;i<=n;++i) a[m]+=a[m-i];
        if(a[m]>1e18) break;
    }
    --m;
    rep(i,n+1,m) s[i]=s[i-1]+a[i], g[i].clear();
    while(q--) {
        int x=read();
        printf("%lld\n",dfs(x,m));
    }
}
signed main() {
    T=read();
    while(T--) solve();
}

luogu8658 [蓝桥杯 2017 国 A] 填字母游戏

我们用分别用 $1$，$-1$，$0$ 表示胜利、失败、平局。

对于一个状态 $S$，它的胜负状态可以表示

$$
f(S) = \max_{S \rightarrow S’ }\Big\{-f(S’)\Big\}
$$

一旦 $f(S)$ 被更新为 $1$，那就直接返回。

然而极限状态数还是 $O(3^{len})$，无法承受，但是这种东西重叠状态数很大，记忆化的效果很好。状态是字符串，可以用std::unordered_map<string,int>实现。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=22;
int T, n;
string s;
unordered_map<string,int> p;
int dfs(string st) {
    if(p.count(st)) return p[st];
    for(int i=0;i<st.size()-2;++i) {
        if(st[i]=='L'&&st[i+1]=='O'&&st[i+2]=='L') {
            return p[st]=-1;
        }
    }
    p[st]=-1;
    int cnt=0;
    for(int i=0;i<st.size();++i) {
        if(st[i]=='*') {
            string t=st;
            t[i]='O';
            p[st]=max(p[st],-dfs(t));
            if(p[st]==1) return 1;
            t[i]='L';
            p[st]=max(p[st],-dfs(t));
            if(p[st]==1) return 1;
            ++cnt;
        }
    }
    if(cnt==0) p[st]=max(p[st],0ll);
    return p[st];
}
void solve() {
    cin>>s;
    if(s.size()<3) { puts("0"); return; }
    for(int i=0;i<s.size()-2;++i) if(s[i]=='L'&&s[i+1]=='O'&&s[i+2]=='L') { puts("1"); return; }
    printf("%lld\n",dfs(s));
    p.clear();
}
signed main() {
    T=read();
    while(T--) solve();
}

luogu3257 [JLOI2014] 天天酷跑

上古老题了，题面有很多叙述不严谨的地方。

首先能发现不管跳不跳，横坐标每次至少增加 $1$，而跳跃过程是容易刻画的。并且 $m$ 和最多连跳数很小，可以直接枚举。

设 $f(x,y,z)$ 表示在 $(x,y)$，已经连跳了 $j$ 次的最大值。

有一些小细节：

  1. 初始点是 $(0,1)$。
  2. 注意跳跃的最高点的贡献不要算重。

用记忆化搜索相对容易实现。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define psb push_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=1e5+5;
int n, m, cnt, h, ans=-1e9, cost1, cost2, a[N][22];
int f[N][22][7];
int dfs(int x,int y,int z) {
    if(x>n||y>m||y<1) return 0;
    if(a[x][y]==-1) return -1e9;
    if(~f[x][y][z]) return f[x][y][z];
    int& res=f[x][y][z];
    res=-1e9;
    if(y==1) z=0;

    if(z<cnt&&y+h<=m) {
        int sum=0, t=0;
        for(int i=1;i<h;++i) {
            if(a[x+i][y+i]==-1) { t=1; break; }
            sum+=a[x+i][y+i]; 
        }
        if(!t) res=max(res,sum+dfs(x+h,y+h,z+1));
        // a[x][y]放到最后算了，所以这里只算前h-1个的贡献
        // 而且在跳跃完成，下落之前，也是可以连跳的
    }
    if(y==1) res=max(res,dfs(x+1,y,z));
    else res=max(res,dfs(x+1,y-1,z));
    return res+=a[x][y];
}
signed main() {
    n=read(), m=read(), cost1=read(), cost2=read();
    rep(j,1,m) rep(i,1,n) a[i][j]=read();
    int ii=0, hh=0;
    for(cnt=1;cnt<=5;++cnt) {
        for(h=1;h*cnt<m;++h) {
            SET(f,-1);
            int res=dfs(0,1,0)-(h-1)*cost1-(cnt-1)*cost2;
            if(res>ans) ans=res, ii=cnt, hh=h;
        }
    }
    if(ans>=0) printf("%d %d %d\n",ans,ii,hh);
    else puts("mission failed");
}

luogu4962 朋也与光玉

$k$ 很小，考虑状压之。

并且在图上走过的路径长度不会超过 $k$，所以直接枚举起点开搜就行。

设 $f(x,S)$ 表示到达节点 $x$，已经收集的元素集合为 $S$ 时的最短路，可以直接通过。

然而本题重叠状态数不多，这时候如果使用上文提到的第二种记忆化方法，那么就能优化搜索顺序，优先搜索权值小的边，这样就能卡进 400ms。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=105;
int n, m, k, U, res, ans=1e9, id, a[N], f[N][1<<13];
vector<PII > p[N];
void dfs(int x,int S,int sum,int dep) {
    if((f[x][S]&&f[x][S]<=sum)) return;
    f[x][S]=sum;
    if(sum>=ans) return;
    if(S==U) { ans=sum; return; }
    if(dep==k) return;
    for(auto t:p[x]) {
        int y=t.fi, z=t.se;
        if(S&(1<<a[y])) continue;
        dfs(y,S|(1<<a[y]),sum+z,dep+1);
    }
}
bool cmp(PII a,PII b) {
    if(a.se!=b.se) return a.se<b.se;
    return a.fi<b.fi;
}
signed main() {
    n=read(), m=read(), k=read();
    U=(1<<k)-1;
    rep(i,1,n) a[i]=read();
    rep(i,1,m) {
        int x=read(), y=read(), z=read();
        p[x].pb({y,z});
    }
    rep(x,1,n) sort(p[x].begin(),p[x].end(),cmp);
    rep(i,1,n) dfs(i,1<<a[i],0,1);
    if(ans!=1e9) printf("%d\n",ans);
    else puts("Ushio!");
}

luogu4796 [BalticOI 2018] 路径

差不多一样的套路，$k$ 很小，设 $f(x,S)$ 为到达节点 $x$，颜色集合为 $S$，还能够产生的路径条数。

注意当 $|S|=1$ 时 $f(x,k)$ 初始值为 $0$，否则为 $1$。

然后就直接做了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=3e5+5;
int n, m, k, U, a[N];
ll ans, f[N][1<<5];
vector<int> p[N];
int lowbit(int x) { return x&-x; }
ll dfs(int x,int S) {
    if(f[x][S]) return f[x][S];
    ll& res=f[x][S];
    res=1;
    if(S==lowbit(S)) res=0;
    if(S==U) return res;
    for(auto y:p[x]) {
        if(S&(1<<a[y])) continue;
        res+=dfs(y,S|(1<<a[y]));
    }
    return res;
}
signed main() {
    n=read(), m=read(), k=read();
    U=(1<<k)-1;
    rep(i,1,n) a[i]=read()-1;
    rep(i,1,m) {
        int x=read(), y=read();
        p[x].pb(y), p[y].pb(x);
    }
    rep(i,1,n) ans+=dfs(i,1<<a[i]);
    printf("%lld\n",ans);
}

部分分

搜索主要的作用是拿部分分。

luogu7961 [NOIP2021] 数列

前 10 个点 $m$ 比较小，$S$ 的范围也不会很大，考虑直接设 $f(x,S’)$ 表示已经确定了 ${a_i}$ 的前 $x$ 项，$S=S’$，还能产生的方案数。$$f(x,S’) = \sum_{i=0}^m v_i \times f(x+1,S’+2^i)$$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=35, M=105, mod=998244353;
int n, m, k, v[M], f[N][1<<18];
int popcount(int x) {
    int cnt=0;
    while(x) cnt+=x&1, x>>=1;
    return cnt;
}
int dfs(int x,int S) {
    if(~f[x][S]) return f[x][S];
    if(x==n) return f[x][S]=popcount(S)<=k;
    int& res=f[x][S];
    res=0;
    for(int i=0;i<=m;++i) {
        (res+=v[i]*dfs(x+1,S+(1<<i)))%=mod;
    }
    return res;
}
signed main() {
    n=read(), m=read(), k=read();
    rep(i,0,m) v[i]=read();
    SET(f,-1);
    printf("%lld\n",dfs(0,0));
}

luogu8817 [CSP-S 2022] 假期计划

这题官方数据过水，以洛谷数据为准。

用 $n$ 次 $\text{BFS}$ 求出多源最短路。

设 $f(x,cnt)$ 为以 $x$ 结尾，选择了 $cnt$ 个点的最大值。这显然是不满足最优子结构性质的：无法知道已经选过了哪些点。使用第一种记忆化方法显然是错的，而第二种做法在选点情况不同时也无法保证到达 $(x,cnt)$ 且当前值小于 $f(x,cnt)$ 最终不会更新答案。

然而这个竟然能通过 $\mathfrak{CCF}$ 的数据。

事实上这个搜索加上乱搞做法然后极致卡时，就能通过所有数据。不过非正解就不细说了。

下面的代码可以通过官方数据，洛谷数据会 WA 一个。

void bfs(int s) {
    queue<int> q;
    rep(i,1,n) dis[s][i]=1e9;
    dis[s][s]=0;
    q.push(s);
    while(q.size()) {
        int x=q.front(); q.pop();
        for(auto y:p[x]) {
            if(dis[s][y]!=1e9) continue;
            dis[s][y]=dis[s][x]+1;
            q.push(y);
        }
    }
}
void dfs(int x,int cnt,int sum) {
    if(f[x][cnt]!=0&&f[x][cnt]>=sum) return;
    int& res=f[x][cnt];
    res=sum;
    if(cnt==5) { ans=max(ans,sum); return; }
    if(cnt==4) {
        if(dis[1][x]<=k+1) dfs(1,5,sum);
        return;
    }
    for(int y=2;y<=n;++y) if(x!=y&&!v[y]&&dis[x][y]<=k+1) {
        v[y]=1;
        dfs(y,cnt+1,sum+a[y]);
        v[y]=0;
    }
}
signed main() {
    n=read(), m=read(), k=read();
    rep(i,2,n) a[i]=read();
    rep(i,1,m) {
        int x=read(), y=read();
        p[x].pb(y), p[y].pb(x);
    }
    rep(i,1,n) bfs(i);
    dfs(1,0,0);
    printf("%lld\n",ans);
}

LOJ#539. 「LibreOJ NOIP Round #1」旅游路线

观察那张大表格。

考虑前 12 个点，发现有 $q_i \le 100$ 和 $C,c_i \le 10^3$，而 $d_i$ 范围相对大。

设 $f(x,qt,ct)$ 表示到达节点 $x$，还剩下 $qt$ 的钱，$ct$ 的油，还能走的最大距离。

这个状态是个 $\text{DAG}$，所以用记忆化搜索转移 DP 即可。$$f(x,qt,ct) = \max \begin{cases}f(y,qt,ct-1)+z & ct > 0\f (x,qt-p_x,\min{ c_x,C}) & qt \ge p_x \text{ and } ct < c_x\end{cases}$$ 对于一个询问 $(s_i,q_i,d_i)$，枚举剩下多少钱，判断是否满足 $d_i$ 的条件即可。

显然具有单调性，可以二分答案优化，不过没必要。

官方题解说这个做法能得到 $60 \text{ pts}$，不过可能是因为数据不给力，实际得分 $75 \text{ pts}$。

复杂度 $\mathcal{O} \Big((n+m)C\max{q_i} + Tq_i \Big)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=105, M=1e5+5;
int n, m, C, T, ww[N][N], p[N], c[N];
int f[N][505][1005];
vector<PII > g[N];
int dfs(int x,int qt,int ct) {
    if(~f[x][qt][ct]) return f[x][qt][ct];
    int& res=f[x][qt][ct];
    res=0;
    if(ct<c[x]&&qt>=p[x]) res=max(res,dfs(x,qt-p[x],min(c[x],C)));
    for(auto t:g[x]) {
        int y=t.fi, z=t.se;
        if(ct) res=max(res,z+dfs(y,qt,ct-1));
    }
    return res;
}
signed main() {
    n=read(), m=read(), C=read(), T=read();
    rep(i,1,n) p[i]=read(), c[i]=read();
    rep(i,1,m) {
        int x=read(), y=read(), z=read();
        ww[x][y]=max(ww[x][y],z);
        // 可能有重边，取最大边权。
    }
    rep(i,1,n) rep(j,1,n) if(ww[i][j]) g[i].pb({j,ww[i][j]});
    SET(f,-1);
    while(T--) {
        int s=read(), q=read(), d=read();
        int ans=-1;
        for(int i=q-1;~i;--i) if(q-i>=p[s]) {
            int t=dfs(s,q-i-p[s],min(c[s],C));
            if(t>=d) { ans=i; break; }
        }
        printf("%lld\n",ans);
    }
}

luogu8163 [JOI 2022 Final] 铁路旅行 2

使用单调队列，我们能求出从每个 $i$ 出发能到达的最左点 $tl_i$ 与最右点 $tr_i$。

一个 $\mathtt{Navie}$ 的结论：任何时候能到达的点都是一个区间，并且这个区间单调扩大。

我们把换乘作为边，边权都是 $1$。在图上 BFS时维护当前区间，维护全局左右端点 $l,r$，对于节点 $i$，将 $[\min(l,tl_i),\max(r,tr_i)]$ 中的节点入队，同时更新 $l$ 为 $\min{tl_i}$，$r$ 为 $\max{tr_i}$。当终点第一次被 $[l,r]$ 包含时，路径长度就是答案。

这样做的复杂度是 $O(n)$ 的，可以得到 $27 \text{ pts}$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=2e5+5;
int n, k, m, Q, a[N], b[N], tl[N], tr[N], tl1[N], tr1[N];
int q[N];
bool v[N];
int bfs(int s,int t) {
    rep(i,1,n) v[i]=0;
    queue<PII > q;
    q.push(MP(s,1));
    int l=s, r=s;
    while(q.size()) {
        int x=q.front().fi, y=q.front().se; q.pop();
        if(v[x]) continue;
        v[x]=1;
        if(s<t&&tr[x]>=t) return y;
        if(s>t&&tl[x]<=t) return y;
        for(int i=r+1;i<=tr[x];++i) if(!v[i]) {
            q.push(MP(i,y+1));
        }
        r=max(r,tr[x]);
        for(int i=l-1;i>=tl[x];--i)if(!v[i]) {
            q.push(MP(i,y+1));
        }
        l=min(l,tl[x]);
    }
    return -1;
}
signed main() {
    n=read(), k=read(), m=read();
    rep(i,1,n) tr[i]=tl[i]=tl1[i]=tr1[i]=i;
    rep(i,1,m) {
        a[i]=read(), b[i]=read();
        if(a[i]<b[i]) tr[a[i]]=tr1[a[i]]=max(tr1[a[i]],b[i]);
        else tl[a[i]]=tl1[a[i]]=min(tl1[a[i]],b[i]);
    }
    int l=1, r=0;
    rep(i,1,n) {
        while(l<=r&&q[l]<i-k+1) ++l;
        if(l<=r) tr[i]=max(tr[i],tr1[q[l]]);
        while(l<=r&&tr1[q[r]]<tr1[i]) --r;
        q[++r]=i;
    }
    l=1, r=0;
    per(i,n,1) {
        while(l<=r&&q[l]>i+k-1) ++l;
        if(l<=r) tl[i]=min(tl[i],tl1[q[l]]);
        while(l<=r&&tl1[q[r]]>tl1[i]) --r;
        q[++r]=i;
    }
    Q=read();
    while(Q--) {
        int s=read(), t=read();
        printf("%lld\n",bfs(s,t));
    }
}

luogu9375 「DROI」Round 2 划分

对于 $\text{subtask 1}$，只需要枚举每个数是接在前面还是新开一段，然后扫一遍统计答案，复杂度 $O(n2^n)$。

观察 $\text{subtask 2}$，总的段数 $m$ 不超过 $20$，那么直接把它们状压了，把划分区间放置区间，从前往后放，同时预处理任意区间的答案，复杂度可以做到 $O(m2^m)$。

观察 $\text{subtask 3}$，区间长度最多只有 $5$ 种，数量算一下也不会很多，仿照乌龟棋就能做了。

这就有了 $50 \text{ pts}$。

// Problem: P9375 「DROI」Round 2 划分
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9375
// Author: KisaragiQwQ
// Date: 2023-06-25 15:20:38
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// 
// Let's Daze
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=128, M=1e6+5, NN=1<<21;
int n, ans, m, mx, ss, a[N], c[N], bel[N];
int squ[20005], v[N][N];
namespace sub3 {
    int U, g[NN];
    int dfs(int S) {
        if(~g[S]) return g[S];
        g[S]=0;
        int T=U^S, sum=1;
        for(int i=0;i<m;++i) if(S&(1<<i)) sum+=bel[i];
        for(int i=0;i<m;++i) if(T&(1<<i)&&sum+bel[i]-1<=n) {
            g[S]=max(g[S],dfs(S|(1<<i))+v[sum][sum+bel[i]-1]);
        }
        return g[S];
    }
    void solve() {
        U=(1<<m)-1;
        SET(g,-1);
        printf("%lld\n",dfs(0));
    }
};
namespace sub4 {
    int g[55][26][18][15][15];
    int dfs(int c1,int c2,int c3,int c4,int c5) {
        if(~g[c1][c2][c3][c4][c5]) return g[c1][c2][c3][c4][c5];
        int& res=g[c1][c2][c3][c4][c5];
        res=0;
        int sum=c[1]-c1+2*(c[2]-c2)+3*(c[3]-c3)+4*(c[4]-c4)+5*(c[5]-c5)+1;
        if(c1>0) res=max(res,dfs(c1-1,c2,c3,c4,c5)+v[sum][sum]);
        if(c2>0) res=max(res,dfs(c1,c2-1,c3,c4,c5)+v[sum][sum+1]);
        if(c3>0) res=max(res,dfs(c1,c2,c3-1,c4,c5)+v[sum][sum+2]);
        if(c4>0) res=max(res,dfs(c1,c2,c3,c4-1,c5)+v[sum][sum+3]);
        if(c5>0) res=max(res,dfs(c1,c2,c3,c4,c5-1)+v[sum][sum+4]);
        return res;
    }
    void solve() {
        SET(g,-1);
        g[0][0][0][0][0]=0;
        printf("%lld\n",dfs(c[1],c[2],c[3],c[4],c[5]));
    }
};
void prework() {
    for(int i=0;i*i<=mx;++i) squ[i*i]=1;
    for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) {
        int x=0, y=0;
        for(int k=i;k<=j;++k) {
            if(squ[abs(a[k]-a[i])]) ++x;
            if(squ[abs(a[j]-a[k])]) ++y;
        }
        v[i][j]=x*y;
    }
}
signed main() {
    n=read();
    rep(i,1,n) a[i]=read(), mx=max(mx,a[i]);
    int fg=1;
    rep(i,1,n) {
        c[i]=read(), ss+=i*c[i];
        if((i>5&&c[i]!=0)) fg=0;
        int t=c[i];
        while(t--) bel[m++]=i;
    }
    if(ss!=n) puts("-1"), exit(0);
    prework();
    if(fg) sub4::solve(); else sub3::solve();
    // sub3::solve();
    return 0;
}

然而正解就比较人类智慧了。

注意到所有 $c_i$ 构成的一个集合，其中元素的总和是不断变小的，然后放置区间是一个很能 $\text{DP}$ 的过程。假定我们有一种哈希方法能唯一表示一个集合的状态，状态的数量却不是很容易计算，如果数量过多，那么这种做法也就没有意义了。

教练用搜索剪枝和一些奇技淫巧，用时 5 min 跑出了 $n=120$ 的状态总数，我记得好像也就 $10^6$？

貌似用 GF 算一下也行，但是手算有点逆天。

由于每个 $c_i$ 单调不增，所以我们这样进行一个进制哈希。

pre[0]=1;
for(int i=1;i<=n;++i) pre[i]=pre[i-1]*(q.c[i]+1);

struct node { int c[N]; } q;

int vary(node x) {
    int id=0;
    for(int i=1;i<=n;++i) id+=x.c[i]*pre[i-1];
    return id;
}

记忆化搜索即可。

namespace sub2 {
    int dfs(node x) {
        int S=vary(x);
        if(~f[S]) return f[S];
        f[S]=0;
        int sum=0;
        for(int i=1;i<=n;++i) sum+=i*x.c[i];
        if(sum==0) return 0;
        for(int i=1;i<=n;++i) if(x.c[i]>0) {
            node y=x;
            --y.c[i];
            f[S]=max(f[S],dfs(y)+v[sum-i+1][sum]);
        }
        return f[S];
    }
    void solve() {
        printf("%lld\n",dfs(q));
    }
};

这部分未完待续。

DP搜索状态压缩
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇