AtCoder DP Contest

atcoder DP 刷题

---

题单链接

Frog 1

设 $dp[i]$ 表示到 $i$ 石头的最小费用

$$dp[1]=0 \\ dp[2]=dp[1]+|h_1-h_2|\\ dp[i]=\min(dp[i-1]+|h_i-h_{i-1}|,dp[i-2]+|h_i,h_{i-2}|) \\ $$

$O(n)$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N];
int n;
int h[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    dp[1]=0,dp[2]=abs(h[2]-h[1]);
    for(int i=3;i<=n;i++){
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i-2]-h[i]));
    }
    cout<<dp[n];
}

Frog 2

状态同上题

$$dp[1]=0\\ dp[i]=\min^{i}_{j=\max(1,i-k)}dp[j]+|h_i-h_{j}|$$

$O(nk)$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N];
int n,k;
int h[N];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>h[i],dp[i]=INT_MAX;
    dp[1]=0;
    for(int i=2;i<=n;i++){
        for(int j=max(1,i-k);j<=i;j++)
           dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i]);
    }
    cout<<dp[n];
}

Knapsack 1

即01背包

还是从最最普通的背包开始，不优化

设 $dp[i][j]$ 表示选到第 $i$ 个物品，占了 $j$ 的空间的最大价值

$$dp[i][j]=\max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])$$

然后注意到这个 $i$ 他皮用没有可以考虑压一压

考虑到第一维一直递增，第二维只跟比他小的有关，于是我们从大到小更新

$$dp[j]=\max(dp[j],dp[j-w[i]]+v[i])$$
枚举时从 $M\to w[i]$ 枚举

$O(nW)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int dp[N];
int n,W;
int w[N],v[N];
signed main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=W;j>=w[i];j--)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
    cout<<dp[W];
}

Grid 1

设 $dp[i][j]$ 表示从 $(1,1)$ 走到 $(i,j)$ 的方案数

容易写出转移 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$

如果当前点是#那就跳过去不转移

初始状态为设 $dp[0][1]=1$ 或者 $dp[1][0]=1$，只设一个

$O(nm)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=1e4+5;
int dp[N][N];
int n,m;
char s[N][N];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }
    dp[0][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#') continue;
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
        }
    }
    cout<<dp[n][m];
}

Vacation

翻译有误，是两天不是两天以上

设 $dp[i][j]$ 表示 $i$ 天进行 $j$ 活动

方程易写出，懒得放了，见代码

$O(n)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=1e5+5;
int dp[N][3];
int n;
int a[N],b[N],c[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
    }    
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}

Knapsack 2

啊我们发现这个题意是个板子的01背包，但是我们发现复杂度不太合理

这个特别小的代价范围给了我们一个想法

设 $dp[i][j]$ 表示到第 $i$ 个物品为止，获得 $j$ 的收益的最小重量

转移类似

$$dp[i][j]=min(dp[i-1][j-v[i]]+w[i])$$

依旧可以压成一维

$dp[j]=\max(dp[j],dp[j-v[i]]+w[i])$,从大往小扫

结束后从大到小找出第一个重量合法的 $v$

复杂度 $O(nV)$，$V$ 是收益和的上界

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int dp[N];
int n,W;
int w[N],v[N];
signed main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int j=1;j<=100000;j++) dp[j]=INT_MAX;
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=n*1000;j>=v[i];j--)
            dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
    }
    for(int i=100000;i>=0;i--){
        if(dp[i]<=W){
            cout<<i;
            return 0;
        }
    }
}

LCS

讨厌的字符串

首先不去考虑路径，考虑求出长度

设 $dp[i][j]$ 表示到 $s_i,t_j$ 为止的 LCS 长度

转移：

$$\begin{cases} dp[i][j]=dp[i-1][j-1]+1 & \text{ if } s_i=t_i \\ dp[i][j]=max(dp[i][j-1],dp[i-1][j]) & \text{ if } s_i\neq t_i \end{cases}$$
至于序列怎么求，记录每个位置是从哪里转移来的，从 $(n,m)$ 反着跑回去就行辣

复杂度 $O(nm)$，分别为两个字符串的长度

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
char s[3005],t[3005];
int n,m;
int dp[3005][3005];
signed main(){
    cin>>(s+1);
    cin>>(t+1);
    n=strlen(s+1);
    m=strlen(t+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        }
    }
    char ans[3005];
    int tt=0;
    for(int i=n,j=m;dp[i][j]>0;){
        if(s[i]==t[j]) ans[dp[i][j]]=s[i],i--,j--;
        else if(dp[i][j-1]>dp[i-1][j]) j--;
        else i--;
    }
    for(int i=1;i<=dp[n][m];i++)
        cout<<ans[i];
}

Longest Path

实在是太愚蠢了，记忆化搜索即可

复杂度 $O(n)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int dp[N];
vector<int> to[N];
int n,m;
int ans;
int dfs(int now){
    if(dp[now]!=-1){
        return dp[now];
    }
    for(int v:to[now]){
        dp[now]=max(dfs(v),dp[now]);
    }
    dp[now]++;
    return dp[now];
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) dp[i]=-1;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        to[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dfs(i));
    }
    cout<<ans;
}

Stones

一类博弈问题的基本思路

设 $dp[i]$ 表示 $i$ 状态是先手必胜 $1$ 还是先手必败 $0$

$dp[0]$ 是初必败态

而所有能指向必败态的都是必胜态

所以从小到大枚举，刷表法更新后面的是必胜还是必败

复杂度 $O(nk)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int dp[N];
int n;
int A[N];
int k;
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    dp[0]=0;
    for(int i=0;i<=k;i++){
        if(!dp[i]){
            for(int j=1;j<=n;j++){
                if(i+A[j]<=k)dp[i+A[j]]=1;
            }
        }
    }
    if(dp[k]){
        cout<<"First";
    }
    else cout<<"Second";
}   

Deque

草了，写线性dp写魔怔了半天没想出来这题

注意到任意时刻剩下的数一定是若干个连续的数，即原数组中的一个区间 $[l,r]$

尝试依据这个来设计状态

设 $f[i][j]$ 表示当前区间 $[l,r]$，能造成的最大差

这边需要注意的是，什么情况对这个差造成的是正贡献，什么时候是负贡献

那就必须要关注是谁正在操作

当前区间长度为 $r-l+1$，二总长度为 $n$，一次操作会换人并且让长度 $-1$

于是当前的人是谁就可以用 $n+l-r-1$ 表达，当这个数是偶数的时候是先手者操作，奇数就是后手者

区间dp的常见格式是先枚举长度再枚举起点，保持相同的写法习惯有利于调题目，更有利于养成习惯

转移方程式给出：

if((n-len)&1)  dp[l][r]=min(dp[l][r-1]-a[r],dp[l+1][r]-a[l]);
else dp[l][r]=max(dp[l][r-1]+a[r],dp[l+1][r]+a[l]);

完整代码，复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int dp[N][N];
int n;
int a[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int len=1;len<=n;len++){
        for(int l=1;n-l+1>=len;l++){
            int r=len+l-1;
            if((n-len)&1)  
                dp[l][r]=min(dp[l][r-1]-a[r],dp[l+1][r]-a[l]);
            else dp[l][r]=max(dp[l][r-1]+a[r],dp[l+1][r]+a[l]);
        }
    }
    cout<<dp[1][n];
}   

Slimes

第一反应这不是贪心！合并果子

仔细秒一眼发现只能相邻

考虑区间 $dp$

设 $dp[l][r]$ 表示把 $[l,r]$ 全部合并的最小代价

但是这道题跟上一题有一个不是很一样的地方，这题明显不能只枚举开头结尾，我们还需要枚举一个断点，考虑把断点左右两边合并起来

方程见代码吧，用前缀和优化一下

复杂度 $O(n^3)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=400+5;
int dp[N][N];
int n;
int a[N];
int sum[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=i;j<=n;j++)dp[i][j]=LONG_LONG_MAX;
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)dp[i][i]=0;
    for(int len=1;len<=n;len++){
        for(int l=1;n-l+1>=len;l++){
            int r=len+l-1;
            for(int k=l;k<=r;k++){
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    cout<<dp[1][n];
}   

Coins

概率dp，第一眼感觉没有绿，顶多中位黄题

设 $dp[i][k]$ 表示前 $i$ 个数有 $k$ 个正面的概率

$$dp[i][k]=dp[i-1][k-1]*p[i]+dp[i-1][k]*(1-p[i])$$

注意精度

复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3000+5;
double dp[N][N];
double p[N];
int n;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){            
        dp[i][0]=dp[i-1][0]*(1-p[i]);
        for(int k=1;k<=i;k++){
            dp[i][k]=dp[i-1][k-1]*p[i]+dp[i-1][k]*(1-p[i]);
        }
    }
    double ans=0;
    for(int i=n/2+1;i<=n;i++){
        ans+=dp[n][i];
    }
    printf("%.10lf",ans);
}   

Sushi

设 $dp_{i,j,k}$ 表示剩 $i$ 个 $1$ 盘子， $j$ 个 $2$ 盘子， $k$ 个 $3$ 盘子的期望

考虑单步期望：

1. 吃 $0$ 个寿司，期望为 $(dp_{i,j,k}+1)\times \frac{n-i-j-k}{n}$

2. 吃 $1$ 个，期望为 $(dp_{i-1,j,k}+1) \times\frac{i}{n}$

3. 吃 $2$ 个，期望为 $(dp_{i+1,j-1,k}+1)\times \frac{j}{n}$

4. 吃 $3$ 个，期望为 $(dp_{i,j+1,k-1}+1)\times \frac{k}{n}$

综上可得转移为

$$dp_{i,j,k}=1+dp_{i,j,k}\times \frac{n-i-j-k}{n}+dp_{i-1,j,k} \times\frac{i}{n}+dp_{i+1,j-1,k}\times \frac{j}{n}+dp_{i,j+1,k-1}\times \frac{k}{n}$$

移项合并

$$dp_{i,j,k}=\frac{n}{i+j+k}+dp_{i-1,j,k} \times\frac{i}{i+j+k}+dp_{i+1,j-1,k}\times \frac{j}{i+j+k}+dp_{i,j+1,k-1}\times \frac{k}{i+j+k}$$

然后注意一下拓扑序，发现要先枚举 $k$ 然后 $j$ 然后 $i$

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N=305;
int n;
db f[N][N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    int c1=0,c2=0,c3=0,a;
    for(int i=1;i<=n;++i){
        cin>>a;
        if(a==1) ++c1;
        if(a==2) ++c2;
        if(a==3) ++c3;
    }
    for(int k=0;k<=n;++k){
        for(int j=0;j<=n;++j){
            for(int i=0;i<=n;++i){
                if(!i&&!j&&!k) continue;
                if(i) f[i][j][k]+=i*f[i-1][j][k];
                if(j) f[i][j][k]+=j*f[i+1][j-1][k];
                if(k) f[i][j][k]+=k*f[i][j+1][k-1];
                f[i][j][k]=(f[i][j][k]+n)/(db)(i+j+k);
            }
        }
    }   
    printf("%.10lf",f[c1][c2][c3]);
    return 0;
}

Candies

设 $dp[i][j]$ 表示到 $i$ 个人，分掉了 $j$ 个糖的方案数

好唐的题

显然 $dp[i][j]=\sum_{t=\max(0,j-a[i])}^{j} dp[i-1][t]$

于是我们获得了一个 $O(nK^2)$ 的优秀做法(并非优秀)

然后我们容易发现右边那依托东西看起来就可以前缀和搞一下,然后我们发现突然做完了

$O(nK)$,顺手优化了一下空间

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[100005];
int n,K;
int a[105];
int s[100005];
signed main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[0]=1;
    s[0]=dp[0];
    for(int j=1;j<=K;j++) s[j]=s[j-1]+dp[j],s[j]%=mod;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=K;j++){
            int t=max(0ll,j-a[i]);
            dp[j]=s[j];
            if(t!=0) dp[j]=(dp[j]-s[t-1]+mod)%mod;
        }
        s[0]=dp[0];
        for(int j=1;j<=K;j++) s[j]=s[j-1]+dp[j],s[j]%=mod;
    }
    cout<<dp[K];
}

Independent Set

考虑设状态 $f[i][j]$ 其中 $j=0 or 1$

表示 $i$ ,$i$ 自己是不是黑点的方案数

$$\begin{cases} f[u][0]=\prod_{x\in son_u} f[x][0]+f[x][1]\\ f[u][1]=\prod_{x\in son_u} f[x][0] \end{cases}$$

$O(n)$

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define int long long
const int mod=1e9+7;
int n;
vector<int> to[200005];
int D[200005][2];
int dp(int now,bool is_black,int fa){
    int ans=1;
    if(D[now][is_black]) return D[now][is_black];
    if(is_black){
        for(int v:to[now]){
            if(v!=fa){
                ans=ans*dp(v,0,now);
                ans%=mod;    
            }
        }
    }
    else{
        for(int v:to[now]){
            if(v!=fa){
                ans=ans*((dp(v,1,now)+dp(v,0,now))%mod);
                ans%=mod;
            }
        }
    }
    return (D[now][is_black]=(ans%mod));
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    cout<<(dp(1,0,0)+dp(1,1,0))%mod;
}

Flowers

发现是一个加权的LIS问题,考虑dp

$dp[i]$ 表示以 $i$ 结尾的最大答案(强制 $i$ 必须选)

$dp[i]=max_{j<i}(dp[j])+a_i$

我们以 $h_i$ 为下标开一个树状数组就可以了,实质上是维护了一个二维偏序

$O(n\log n)$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[200005];
int n,K;
int a[200005];
int h[200005];
int tr[200005];
void add(int i,int x){
    for(;i<=200000;i+=i&(-i)){
        tr[i]=max(tr[i],x);
    }
}
int Max(int i,int res=0){
    for(;i;i-=i&(-i)){
        res=max(res,tr[i]);
    }
    return res;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        dp[i]=Max(h[i]-1)+a[i];
        add(h[i],dp[i]);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

Walk

设 $dp[i][j][k]$ 表示 $i\to j$ 的长度为 $k$ 的路径条数

容易发现 $dp[...][...][1]$ 就是初始图

显然有

$$dp[i][j][k]=\sum dp[i][x][k-1]\times dp[x][j][1]$$

就是,你集中一下注意力,你发现这玩意跟矩阵乘法形式一样

于是上一个矩阵快速幂即可

Matching

先 $2^n$ 搞一下左半点枚举

然后不可能再跑右边点了,那就 $2^{2n}$ 已经死掉了

考虑状压, $dp[S][t]$ 表示前 $t$ 个左点已经和 $S$ 集合中的点完全匹配的方案数

容易发现 $dp[S][t]=\sum dp[S-i][t-1],i\in S$,$S-i$ 指去掉 $i$,就是枚举新的这个左点跟谁匹配

复杂度 $O(2^n n^2)$,换一下循环顺序卡卡常就可以

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define rint register int
#define int long long
const int mod=1e9+7;
int n;
int dp[23][2097154];
int a[23][23];
int to[23][23];
int len[23];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(rint i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j])to[i][++len[i]]=j;
        }
    }
    dp[0][0]=1;
    for(rint t=1;t<=n;t++){ 
        for(rint k=1;k<=len[t];k++){
            for(rint j=0;j<(1<<n);j++){
                int w=to[t][k];
                if(j>>(w-1)){
                    dp[t][j]=(dp[t][j]+dp[t-1][j-(1<<(w-1))])%mod;
                }
            }        
        }
    }
    cout<<dp[n][(1<<n)-1];
}

Digit Sum

简单数位dp, $dfs(now,sum,flg)$ 表示到哪一位,总和($\bmod D$),是否贴着上限

记忆化即可

复杂度不会算 $O(可过)$

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define rint register int
#define int long long
const int mod=1e9+7;
int D;
int f[105][105][2];
int word[100005],cnt;
int dfs(int now,int sum,bool flg){
    if(now<=0){
        return sum==0;
    }
    if(f[now][sum][flg]!=-1) return f[now][sum][flg];
    int up=flg?word[now]:9;
    int wc=0;
    for(int i=0;i<=up;i++){
        wc+=dfs(now-1,(sum+i)%D,(i==up) and flg);
        wc%=mod;
    }
    f[now][sum][flg]=wc;
    return wc;
}
string s;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s;
    for(int i=0;i<s.length();i++) {
        word[++cnt]=s[s.length()-i-1]-'0';
    }
    cin>>D;
    memset(f,-1,sizeof f);
    cout<<dfs(cnt,0,1)-1;
}

Permutation

设 $dp[i][j]$ 表示到 $i$ 位,上一位放 $j$ 的方案数

显然这样信息少了,不能这样

设 $dp[i][j]$ 表示在前 $i$ 位放 $1\to i$ 排列,$i$ 位置填 $j$ 的方案数

那么加入加入一个新的 $j$ 只要把原来比 $j$ 大的全部 $+1$ 做一个映射就变成一个 $i+1$ 的排列了

如果前面是 $>$,$dp[i][j]=\sum_{k=j}^{i-1} dp[i-1][k]$

如果前面是 $<$,$dp[i][j]=\sum_{k=1}^{j-1} dp[i-1][k]$

然后我们可以得到一个 $O(n^3)$ 的dp

前缀和优化一下就可以了

复杂度 $O(n^2)$,空间可以压到 $O(n)$ 但是我比较懒

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define rint register int
#define int long long
const int mod=1e9+7;
int dp[3005][3005];
int n;
string s;
int S[3005];
signed main(){
    cin>>n>>s;
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++) S[j]=S[j-1]+dp[i-1][j],S[j]%=mod;
        for(int j=1;j<=i;j++){
            if(s[i-2]=='<'){
                dp[i][j]=S[j-1];
            }
            else{
                dp[i][j]=(S[i-1]-S[j-1]+mod)%mod;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=dp[n][i];
        ans%=mod;
    }
    cout<<ans;
}

Grouping

设 $dp[S]$ 表示对 $S$ 集合进行划分的最大答案

$dp[S]=\max_{i+j=S}dp[i]+val[j]$

据说复杂度 $O(3^n)$

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define rint register int
#define int long long
const int mod=1e9+7;
int n;
int a[17][17];
int dp[65537];
int C[65537];
int dfs(int now){
    if(!now) return 0;
    if(dp[now]!=-1) return dp[now];
    for(int i=now;i;i=(i-1)&now){//一种枚举子集的写法
        dp[now]=max(dp[now],C[i]+dfs(now-i));
    }
    return dp[now];
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int s=1;s<(1<<n);s++){
        dp[s]=-1;
        for(int i=1;i<=n;i++){
            if((s>>(i-1))&1){
                for(int j=i+1;j<=n;j++){
                    if((s>>(j-1))&1){
                        C[s]+=a[i][j];
                    }
                }
            }
        }
    }
    cout<<dfs((1<<n)-1);
}

Subtree

一点点考虑

假设只以某一个点为根的答案

设 $dp[u]$ 表示在 $u$ 的子树内，强制必须染 $u$ 后联通的方案数

容易推出 $dp[u]=\prod_{v\in son[u]} dp[v]+1$

此外我们还需要维护一个 $f_u$ 表示 $u$ 的子树外，强制染 $u$ 并且联通的方案数，这样答案就是 $dp_u\times f_u$

但我们都知道子树外的信息不是很好维护，于是我们发现如果一个点没有子树外部分就好了

于是考虑换根dp

考虑将根从 $u$ 换到 $v$ 的影响

$dp[u]\leftarrow \dfrac{dp[u]}{dp[v]+1}$

然后

$dp[v]\leftarrow dp[v]\times (1+dp[u])$

结合上面两个式子我们可以得出

$$dp[v]=dp[v]\times(\dfrac{dp[u]}{dp[v]+1}+1)$$

好像做完了，但是有个小小的问题就是

模数不一定是质数

那这个除法就是个大问题了

我们注意到答案的统计其实是乘积形式，那除法就可以理解成直接不加上某一部分

维护前缀后缀积即可

复杂度 $O(n)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,mod,cnt;
int dp[100005],pre[400005],sub[400005];
vector<int> e[100005];
void dfs1(int x,int fa){
    dp[x]=1;
    for(int y:e[x]){
        if(y==fa)continue;
        dfs1(y,x);
        dp[x]=(dp[x]*(dp[y]+1))%mod;
    }
}
void dfs(int x,int fa,int las){
    dp[x]=dp[x]*(las+1)%mod;
    int st=++cnt,en,o=0;
    cnt=cnt+e[x].size()+1;
    pre[st-1]=1,sub[cnt-1]=1;
    en=cnt-2;
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y==fa)pre[st+o]=pre[st+o-1]*(las+1)%mod;
        else pre[st+o]=pre[st+o-1]*(dp[y]+1)%mod;
        o++;
    }
    o=0;
    for(int i=e[x].size()-1;~i;--i){
        int y=e[x][i];
        if(y==fa)sub[en-o]=sub[en-o+1]*(las+1)%mod;
        else sub[en-o]=sub[en-o+1]*(dp[y]+1)%mod;
        o++;
    }
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y==fa)continue;
        dfs(y,x,(pre[st+i-1]*sub[st+i+1])%mod);
    }
}
signed main(){
    cin>>n>>mod;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    dfs1(1,0);
    dfs(1,0,0);
    for(int i=1;i<=n;i++){
        cout<<dp[i]<<'\n';
    }
}

Tower

数据范围有点大，直接dp没有什么前途，拓扑序不确定需要跑 $n$ 次背包很炸裂就

考虑先贪心一下，是一个很典的exchange arguements类型的贪心，也许拓扑序能够定下来呢

我们考虑相邻两个物品 $i$ 和 $j$

若 $i$ 放 $j$ 下面则在 $j$ 上方能堆 $s[j]-w[i]$，反之为 $s[i]-w[j]$ 的物品

那么当 $w[i]+s[i]\lt w[j]+s[j]$ 时， $i$ 应该被放在下面，按这样排序

然后拓扑序就正常了，可以跑一遍01背包就行了

复杂度 $O(nW)$，大概吧

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,W=2e4+5;
int n;
long long dp[N][W];
struct node{
    int w,s;
    long long v;
}a[N];
bool cmp(node x,node y){
    return x.s+x.w<y.s+y.w;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].w>>a[i].s>>a[i].v;
    }
    sort(a+1,a+n+1,cmp);
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<W;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=a[i].w and j-a[i].w<=a[i].s){
                dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].w]+a[i].v);
            }
        }
    }
    long long ans=0;
    for(int i=0;i<W;i++){
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<'\n';
    return 0;
}

Grid 2

都不用想暴力dp，空间爆炸时间爆炸没有什么优化空间

看到 $n$ 的范围很健康，考虑关于关键点设计dp

设 $dp_i$ 表示到第 $i$ 个关键点，不经过任何障碍 （除了当前点自己）的方案数

然后考虑容斥,$dp_i=\binom{x_i+y_i-2}{x-1}-\sum_{j=1}^{i-1} dp_j\binom{x_i-x_j+y_i-y_j}{x_i-x_j}$

然后我们把 $(H,W)$ 设为 $n+1$ 号关键点

复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
struct exut{int x,y;}a[3005];
bool cmp(exut x,exut y){
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
int H,W,n;
int dp[3005];
int inv[300005];
int jc[300005];
int pinv[300005];
int C(int x,int y){
    return (jc[x]*pinv[x-y]%mod)*pinv[y]%mod;
} 
signed main(){
    cin>>H>>W>>n;
    inv[1]=pinv[1]=jc[1]=1;
    jc[0]=1,pinv[0]=1;
    for(int i=2;i<=H+W;i++){
        jc[i]=jc[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        pinv[i]=pinv[i-1]*inv[i]%mod;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    a[++n]={H,W};
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        dp[i]=C(a[i].x+a[i].y-2,a[i].x-1);
        for(int j=1;j<i;j++){
            if(a[i].x>=a[j].x and a[i].y>=a[j].y)
               dp[i]=(dp[i]+mod-dp[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)%mod)%mod;
        }
    }
    cout<<dp[n];
}

Intervals

都说是套路....

但是不会一点啊

套路貌似是把区间看成点，在右端点考虑答案，这样子是补充不漏的

考虑状态 $dp_{i,j}$ 表示处理完 $i$ 位置，上一个 $1$ 在 $j$ 的最大答案

单独考虑一个特殊的情况

$$dp_{i,i}=\max_{1\le j<i} f_{i-1,j}+\sum_{k,l_k\le i,r_k=i} val_k$$

其次有

$$dp_{i,j}=dp_{i-1,j}+\sum_{k,l_k\le j,r_k=i} val_k$$

这样做的时空都不是很健康，双 $n^2$ 的复杂度不可能过这道题

空间是简单的，只需要滚一下立马就好了

时间上，我们注意一下当 $i$ 右移一位的时候发生了什么

你细品，其实就是一个区间加一个区间最值，直接上线段树维护吧

 #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int inf=1e17;
int tr[N*4],tag[N*4];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid (l+r>>1)
#define pushup(x) tr[x]=max(tr[ls(x)],tr[rs(x)])
struct node{
    int l,v;
};
vector<node> V[N];
void pushdown(int rt,int l,int r){
    if(!tag[rt]) return ;
    int k=tag[rt];tag[rt]=0;
    tr[ls(rt)]+=k,tr[rs(rt)]+=k;
    tag[ls(rt)]+=k,tag[rs(rt)]+=k;
}
void modi(int rt,int l,int r,int L,int R,int k){
    if(L<=l and r<=R){tr[rt]+=k,tag[rt]+=k;return;}
    if(L>r or l>R) return;
    pushdown(rt,l,r);
    modi(ls(rt),l,mid,L,R,k);
    modi(rs(rt),mid+1,r,L,R,k);
    pushup(rt);
}
int query(){
    return max(tr[1],0ll);
}
int n,m;
signed main(){
    cin>>n>>m;
    while(m--){
        int l,r,w;
        cin>>l>>r>>w;
        V[r].push_back({l,w});
    }
    for(int i=1;i<=n;i++){
        modi(1,1,n,i,i,query());
        for(node v:V[i]){
            modi(1,1,n,v.l,i,v.v);
        }
    }
    cout<<query();
}

Frog 3

状态显然，转移显然

$dp_i=\min_{j=1}^{i-1} dp_j+(h_i-h_j)^2+C$

然后先摘掉 $min$，化一下式子

$$dp_i-h_i^2-C=dp_j+h_j-2h_j h_i$$

这已经是一次函数形式了，李超树维护一下就行了

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef double db;
const int N=2e5+5;
const db eps=1e-9;
db K[N],B[N];   
db F(int now,int x){//哪一条线段在x处的值
    return K[now]*x+B[now];
}
int tr[1000005*4];//线段树每个结点存的是哪条线段（编号）
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
void ins(int rt,int l,int r,int p){//插入编号为p
    if(F(tr[rt],l)>F(p,l) and F(tr[rt],r)>F(p,r)) {tr[rt]=p;return;}
    if(F(tr[rt],l)<=F(p,l) and F(tr[rt],r)<=F(p,r)) {return;}
    if(F(tr[rt],mid)<=F(p,mid)){
        ins(ls,l,mid,p);
        ins(rs,mid+1,r,p); 
    }
    else{
        ins(ls,l,mid,tr[rt]);
        ins(rs,mid+1,r,tr[rt]);
        tr[rt]=p;
    }
}
db query(int rt,int l,int r,int d){
    if(l==r) return F(tr[rt],d);
    if(d<=mid) return min(F(tr[rt],d),query(ls,l,mid,d));
    else return min(F(tr[rt],d),query(rs,mid+1,r,d));
}
int dp[N];
int n,C,h[N];
signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0),cout.tie(0);
    cin>>n>>C;
    for(int i=1;i<=n;i++) cin>>h[i];
    dp[1]=0;
    K[1]=-2*h[1],B[1]=h[1]*h[1];
    ins(1,1,1000000,1);
    for(int i=2;i<=n;i++){
        dp[i]=query(1,1,1000000,h[i])+h[i]*h[i]+C;
        K[i]=-2*h[i],B[i]=dp[i]+h[i]*h[i];
        ins(1,1,1000000,i);
    }
    cout<<dp[n];
}