首页 > 其他分享 >再见了，所有的 Educational DP

再见了，所有的 Educational DP

时间：2024-11-18 22:42:24浏览次数：1  
标签：Educational 再见 int ll cin long using include DP

A - Frog 1

线性 DP。

状态转移方程为

\[f_i = \min(f_{i-1} + \lvert h_i - h_{i-1} \rvert, f_{i-2} + \lvert h_i - h_{i-2} \rvert) \]

，注意边界。

代码 
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5;
int n,a[N];
int f[N];
inline int ABS(int x){return max(x,-x);}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[2]=ABS(a[2]-a[1]);
    for(int i=3;i<=n;i++)
        f[i]=min(f[i-1]+ABS(a[i]-a[i-1]),f[i-2]+ABS(a[i]-a[i-2]));
    cout<<f[n]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

B - Frog 2

线性 DP。

状态转移方程为

\[f_i = \min_{i-k \leq j \lt i} (f_j + \lvert a_i - a_j \rvert) \]

代码 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,m,a[N];
inline int ABS(int x){return max(x,-x);}
int f[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    for(int i=2;i<=n;i++)
        for(int j=max(1,i-m);j<i;j++)
            f[i]=min(f[i],f[j]+ABS(a[i]-a[j]));
    cout<<f[n]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

C - Vacation

线性 DP。

设 \(f_{i,0/1/2}\) 表示前 \(i\) 天，第 \(i\) 天选 A，B，C 的最大幸福值，转移方程为

\[f_{i,0} = \max(f_{i-1,1},f_{i-1,2})+a_i \]

\[f_{i,1} = \max(f_{i-1,0},f_{i-1,2})+b_i \]

\[f_{i,2} = \max(f_{i-1,0},f_{i-1,1})+c_i \]

代码 
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],c[N];
int f[N][3];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++){
        f[i][0]=max(f[i-1][1],f[i-1][2])+a[i];
        f[i][1]=max(f[i-1][0],f[i-1][2])+b[i];
        f[i][2]=max(f[i-1][0],f[i-1][1])+c[i];
    }
    cout<<max(max(f[n][0],f[n][1]),f[n][2])<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

D - Knapsack 1

背包 DP。

设 \(f_{i,j}\) 为前 \(i\) 个物品，背包容量为 \(j\) 的最大价值，状态转移方程为

\[f_{i,j} = \max(f_{i-1,j}, f_{i-1,j-w_i}+v_i) \]

使用滚动数组或者一种广为人知的动态更新可以做到 \(O(W)\) 空间。

代码 
#include<iostream>
#include<cstdio>
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,m;
ll f[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1,v,w;i<=n;i++){
        cin>>w>>v;
        for(int j=m;j>=w;j--)f[j]=max(f[j],f[j-w]+v);
    }
    cout<<f[m]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

E - Knapsack 2

背包 DP。

设 \(f_{i,j}\) 为前 \(i\) 个物品，价值为 \(j\) 的最小容量，状态转移方程为

\[f_{i,j} = \min(f_{i-1,j}, f_{i-1,j-v_i} + w_i) \]

同样可以用滚动数组或者一种广为人知的动态更新可以做到 \(O(Nv)\) 空间。

代码 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,m;
ll f[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1,w,v;i<=n;i++){
        cin>>w>>v;
        for(int j=100000;j>=v;j--)f[j]=min(f[j],f[j-v]+w);
    }
    for(int i=100000;~i;i--)
        if(f[i]<=m)return cout<<i<<endl,0;
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

F - LCS

经典题。

设 \(f_{i,j}\) 为 \(s[1..i]\) 与 \(t[1..j]\) 的 LCS 长度，则转移方程为

\[f_{i,j} = \begin{cases} \max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}), s_i \neq t_j , \\ \max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1} + 1), s_i = t_j . \end{cases} \]

记录转移以输出方案。

代码 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
using pii=pair<int,int>;
const int N=3005;
int n,m;
string s,t;
int f[N][N];
pii pa[N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>s>>t;n=s.size(),m=t.size();s=' '+s,t=' '+t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(f[i][j-1]>f[i-1][j])f[i][j]=f[i][j-1],pa[i][j]={i,j-1};
            else f[i][j]=f[i-1][j],pa[i][j]={i-1,j};
            if(f[i-1][j-1]+(s[i]==t[j])>f[i][j])f[i][j]=f[i-1][j-1]+(s[i]==t[j]),pa[i][j]={i-1,j-1};
        }
    string ans;
    pii p={n,m};
    while(p.first&&p.second){
        pii ne=pa[p.first][p.second];
        if(ne.first==p.first-1&&ne.second==p.second-1&&s[p.first]==t[p.second])ans+=s[p.first];
        p=ne;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

G - Longest Path

DAG 上 DP。

状态转移方程为

\[f_v = \max_{\{u \mid \exists (u,v) \in E \}}(f_u + 1) \]

代码 
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int>gr[N];
int ind[N];
int f[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        gr[u].push_back(v),ind[v]++;
    }
    queue<int>q;
    for(int i=1;i<=n;i++)if(!ind[i])q.push(i);
    while(q.size()){
        int p=q.front();
        q.pop();
        for(auto to:gr[p]){
            f[to]=max(f[to],f[p]+1);
            if(!--ind[to])q.push(to);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

H - Grid 1

状态转移方程为

\[f_{i,j} = \begin{cases} 0, a_{i,j} = \texttt{#} , \\ f_{i-1,j} + f_{i,j-1}, \texttt{otherwise} \end{cases} \]

代码 
#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=1005;
int n,m;
char ch[N][N];
ll f[N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ch[i][j];
    f[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ch[i][j]=='.')(f[i][j]+=f[i-1][j]+f[i][j-1])%=mod;
    cout<<f[n][m]<<endl;
    return 0;
}

I - Coins

期望 DP。

设 \(f_{i,j}\) 为前 \(i\) 个硬币，有 \(j\) 个正面的概率，转移方程为

\[f_{i,j} \gets f_{i-1,j-1} \times p_i + f_{i-1,j} \times (1 - p_i) \]

代码 
#include<iostream>
#include<cstdio>
using namespace std;
using db=double;
const int N=3005;
int n;db a[N];
db f[2][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int cur=0;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        cur^=1;
        for(int j=0;j<=i;j++)f[cur][j]=0;
        f[cur][0]=f[cur^1][0]*(1-a[i]);
        for(int j=1;j<=i;j++)f[cur][j]+=f[cur^1][j]*(1-a[i])+f[cur^1][j-1]*a[i];
    }
    db ans=0;
    for(int i=n/2+1;i<=n;i++)ans+=f[cur][i];
    printf("%.9lf\n",ans);
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

J - Sushi

期望 DP。

设 \(f_{a,b,c}\) 为当前有 \(a\) 个盘子装 \(1\) 个，\(b\) 个盘子装 \(2\) 个，\(c\) 个盘子装 \(3\) 个，期望还要操作几次，可以得出

\[f_{a,b,c} = \frac{a}{n} f_{a-1,b,c} + \frac{b}{n} f_{a+1,b-1,c} + \frac{c}{n} f_{a,b-1,c+1} + \frac{n-a-b-c}{n} f_{a,b,c} + 1 \]

整理得

\[f_{a,b,c} = \frac{a f_{a-1,b,c} + b f_{a+1,b-1,c} + c f_{a,b+1,c-1} + n}{a+b+c} \]

代码 
#include<iostream>
#include<cstdio>
using namespace std;
using db=double;
const int N=305;
int n,a,b,c;
db f[N][N][N];
db dfs(int a,int b,int c){
    if(!a&&!b&&!c)return 0;
    if(a<0||b<0||c<0)return 0;
    if(f[a][b][c]!=-1)return f[a][b][c];
    db&ret=f[a][b][c];ret=0;
    ret=((db)a*dfs(a-1,b,c)+(db)b*dfs(a+1,b-1,c)+(db)c*dfs(a,b+1,c-1)+n)/(db)(a+b+c);
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        if(x==1)a++;
        else if(x==2)b++;
        else if(x==3)c++;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                f[i][j][k]=-1;
    printf("%.9lf\n",dfs(a,b,c));
    return 0;
}
//coder:Iictiw
//date:24/11/07
//When I wrote a piece of code, her and I knew what it was doing

K - Stones

博弈论。

设 \(f_i = 0/1\) 为当前状态先手必败 / 必胜，则有

\[f_i = \bigvee_{1 \leq j \leq n} \neg f_{i-a_j} \]

代码 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,k,a[N];
int f[N];
bool dfs(int k){
    if(f[k]!=-1)return f[k];
    f[k]=0;
    for(int i=1;i<=n;i++)
        if(k>=a[i])f[k]|=!dfs(k-a[i]);
    return f[k];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    memset(f,-1,sizeof(f));
    if(dfs(k))cout<<"First"<<endl;
    else cout<<"Second"<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/14
//When I wrote a piece of code, her and I knew what it was doing

L - Deque

博弈论。

设 \(f_{l,r}\) 为当前序列为 \(a_l \ldots a_r\) 时的结果，转移方程为

\[f_{l,r} = \max(- f_{l+1,r} + a_l, - f_{l,r-1} + a_r) \]

代码 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
using ll=long long;
const int N=3005;
int n,a[N];
ll f[N][N];
inline ll dfs(int l,int r){
    if(l==r)return a[l];
    if(l>r)return 0;
    if(f[l][r]!=-1)return f[l][r];
    return f[l][r]=max(a[l]-dfs(l+1,r),a[r]-dfs(l,r-1));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    memset(f,-1,sizeof(f));
    cout<<dfs(1,n)<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/08
//When I wrote a piece of code, her and I knew what it was doing

M - Candies

前缀和优化 DP。

设 \(f_{i,j}\) 为前 \(i\) 个孩子，分了 \(j\) 个糖果的方案数，有转移

\[\sum_{j-a_i \leq k \leq j} f_{i-1,k} \to f_{i,j} \]

易用前缀和优化至 \(O(NK)\) 时间复杂度。

代码 
#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=105,M=1e5+5;
int n,m,a[N];
int f[2][M],g[M];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[0][0]=1;
    int cur=0;
    for(int i=1;i<=n;i++){
        g[0]=f[cur][0];
        for(int j=1;j<=m;j++)g[j]=(g[j-1]+f[cur][j])%mod;
        cur^=1;
        for(int j=0;j<=m;j++)f[cur][j]=0;
        for(int j=0;j<=m;j++)f[cur][j]=((g[j]-(j-a[i]<=0?0:g[j-a[i]-1]))%mod+mod)%mod;
    }
    cout<<f[cur][m]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/08
//When I wrote a piece of code, her and I knew what it was doing

N - Slimes

区间 DP。

设 $ f_{l,r} $ 为区间 $ [l,r] $ 的最小代价，则转移方程为

\[f_{l,r} = \min_{l \leq i \lt r}(f_{l,i} + f_{i+1,r} + \sum_{l \leq j \leq r} a_j) \]

代码 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
using ll=long long;
const int N=405;
const ll inf=1e16+5;
int n,a[N];ll s[N];
ll f[N][N];
ll dfs(int l,int r){
    if(l>=r)return 0;
    if(f[l][r]!=-1)return f[l][r];
    ll&ret=f[l][r];ret=inf;
    for(int i=l;i<r;i++)
        ret=min(ret,dfs(l,i)+dfs(i+1,r)+s[r]-s[l-1]);
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
    memset(f,-1,sizeof(f));
    cout<<dfs(1,n)<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/08
//When I wrote a piece of code, her and I knew what it was doing

O - Matching

状压 DP。

设 \(f_{S,i}\) 为匹配前 \(i\) 个男性，女性匹配情况为 \(S\) 的方案数，可得转移方程

\[f_{S,i} \to f_{S \cup \{j\},i+1} ( S \cap \{j\} = \varnothing \wedge a_{i,j} = 1 ) \]

代码 
#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=21;
int n,a[N][N];
ll f[1<<N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    for(int i=0;i<n;i++)if(a[0][i])f[1<<i][0]=1;
    for(int i=0;i<n-1;i++)
        for(int S=0;S<(1<<n);S++){
            if(f[S][i]==0)continue;
            for(int j=0;j<n;j++){
                if((S>>j)&1||!a[i+1][j])continue;
                (f[S|(1<<j)][i+1]+=f[S][i])%=mod;
            }
        }
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/08
//When I wrote a piece of code, her and I knew what it was doing

P - Independent Set

树上 DP。

设 \(f_{u,0/1}\) 为以第 \(u\) 个点为根的子树，点 \(u\) 颜色为白 / 黑的方案数，转移方程为

\[f_{u,0} = \prod_{\{v \mid v \in \operatorname{son}(u) \}} f_{v,0} + f_{v,1} \]

\[f_{u,1} = \prod_{\{v \mid v \in \operatorname{son}(u) \}} f_{v,0} \]

代码 
#include<iostream>
#include<cstdio>
#include<vector>
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=1e5+5;
int n;
vector<int>gr[N];
ll f[N][2];
void dfs(int p,int fa){
    f[p][0]=f[p][1]=1;
    for(auto to:gr[p]){
        if(to==fa)continue;
        dfs(to,p);
        (f[p][0]*=f[to][0]+f[to][1])%=mod;
        (f[p][1]*=f[to][0])%=mod;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        gr[u].push_back(v),gr[v].push_back(u);
    }
    dfs(1,0);
    cout<<(f[1][0]+f[1][1])%mod<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/09
//When I wrote a piece of code, her and I knew what it was doing

Q - Flowers

数据结构优化 DP。

设 \(f_{i}\) 为前 \(i\) 朵花，且选择第 \(i\) 朵花的美丽值之和的最大值，有转移

\[f_{i} = \max_{ \{j \mid 1 \leq j \lt i \wedge h_j < h_i \}} f_j + a_i \]

注意到这相当于一个二维偏序，因此可以用 BIT 优化至线性对数时间复杂度。

代码 
#include<iostream>
#include<cstdio>
using namespace std;
using ll=long long;
const int N=2e5+5;
int n,a[N],h[N];
ll f[N];
ll t[N];
inline void update(int i,ll x){for(i++;i<=n+1;i+=i&-i)t[i]=max(t[i],x);}
inline ll query(int i){ll ret=0;for(i++;i;i-=i&-i)ret=max(ret,t[i]);return ret;}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        f[i]=query(h[i]-1)+a[i];
        update(h[i],f[i]);
    }
    cout<<query(n)<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/09
//When I wrote a piece of code, her and I knew what it was doing

R - Walk

矩阵乘法加速 DP。

设 \(f_{i,j}\) 为走了 \(i\) 步，当前在点 \(j\) 的方案数，有转移

\[f_{i,j} = \sum_{\{ k \mid a_{k,j} = 1 \}} f_{i-1,k} \]

可以将转移写成矩阵乘法的形式，做到 \(O(n^3 \log k)\) 。

代码 
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=55;
int n;ll m;
struct matrix{
    ll a[N][N];
    int n,m;
    matrix(){
        n=m=0;
        memset(a,0,sizeof(a));
    }
    friend matrix operator*(matrix a,matrix b){
        matrix c;c.n=a.n,c.m=b.m;
        for(int k=1;k<=a.m;k++)
            for(int i=1;i<=a.n;i++)
                for(int j=1;j<=b.m;j++)
                    (c.a[i][j]+=a.a[i][k]*b.a[k][j])%=mod;
        return c;
    }
};
inline matrix qpow(matrix a,ll p){
    matrix ret;ret.n=a.n,ret.m=a.m;
    for(int i=1;i<=ret.n;i++)ret.a[i][i]=1;
    while(p){
        if(p&1)ret=ret*a;
        a=a*a,p>>=1;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    matrix I,C;C.n=n,C.m=n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>C.a[i][j];
    I.n=1,I.m=n;
    for(int i=1;i<=n;i++)I.a[1][i]=1;
    C=qpow(C,m);
    I=I*C;
    ll ans=0;
    for(int i=1;i<=n;i++)(ans+=I.a[1][i])%=mod;
    cout<<ans<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/09
//When I wrote a piece of code, her and I knew what it was doing

S - Digit Sum

数位 DP。

设 \(f_{i,j}\) 为还有 \(i\) 位未填，数位之和模 \(D\) 等于 \(j\) 的方案数，有转移

\[f_{i,j} = \sum f_{i-1,(j + k) \bmod D} \]

代码 
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=1e4+5;
int n;string s;
ll f[N][105];
int num[N];
ll dfs(int p,int s,bool limit){
    if(!p)return s==0;
    if(!limit&&f[p][s]!=-1)return f[p][s];
    ll ret=0;int up=limit?num[p]:9;
    for(int i=0;i<=up;i++)(ret+=dfs(p-1,(s+i)%n,limit&&i==up))%=mod;
    if(!limit)f[p][s]=ret;
    return ret;
}
ll solve(string s){
    int tot=0;
    for(int i=(int)s.size()-1;i;i--)num[++tot]=s[i]-'0';
    memset(f,-1,sizeof(f));
    return dfs(tot,0,1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>s>>n;s=' '+s;
    cout<<(solve(s)-1+mod)%mod<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/09
//When I wrote a piece of code, her and I knew what it was doing

T - Permutation

前缀和优化 DP。

开始上强度了。

设 \(f_{i,j}\) 为填前 \(i\) 个数，第 \(i\) 个数为 \(j\) ，且前 \(i\) 个数为 \(1\) 到 \(i\) 的排列的方案数，每次加入新的数 \(j\) 时，可以将原来排列中所有大于等于 \(j\) 的数加一以保证仍是排列。不难发现，这样依然满足题目要求的性质。

由此，有转移

\[ f_{i,j} = \begin{cases} \sum_{j \leq k \lt i} f_{i-1,k}, s_{i-1} = \texttt{>} \\ \sum_{1 \leq k \lt j} f_{i-1,k}, s_{i-1} = \texttt{<} \end{cases} \]

不难使用前缀和优化转移。

代码 
#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=3005;
int n;string s;
ll f[N][N],g[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>s;s=' '+s;
    f[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)g[j]=(g[j-1]+f[i-1][j])%mod;
        for(int j=1;j<=i;j++)
            if(s[i-1]=='>')f[i][j]=(g[i-1]-g[j-1]+mod)%mod;
            else f[i][j]=g[j-1];
    }
    ll ans=0;
    for(int j=1;j<=n;j++)(ans+=f[n][j])%=mod;
    cout<<ans<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/10
//When I wrote a piece of code, her and I knew what it was doing

U - Grouping

状压 DP。

设 \(f_S\) 为 \(S\) 中的兔子可得的最高得分，则有转移

\[f_S = \max_{T \subseteq S}(f_{S-T} + g_T) \]

其中， \(g_S\) 为 \(S\) 中的兔子分为一组的得分。

代码 
#include<iostream>
#include<cstdio>
using namespace std;
using ll=long long;
const int N=17;
int n,a[N][N];
ll f[1<<N],g[1<<N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    for(int S=0;S<(1<<n);S++)
        for(int i=0;i<n;i++){
            if(!((S>>i)&1))continue;
            for(int j=i+1;j<n;j++){
                if(!((S>>j)&1))continue;
                g[S]+=a[i][j];
            }
        }
    for(int S=0;S<(1<<n);S++)
        for(int T=S;T;T=S&(T-1))
            f[S]=max(f[S],f[S-T]+g[T]);
    cout<<f[(1<<n)-1]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/11
//When I wrote a piece of code, her and I knew what it was doing

V - Subtree

换根 DP。

设点 \(1\) 为根，\(f_{u}\) 为以 \(u\) 为根的子树的方案数，则有转移

\[f_{u} = \prod_{\{v \mid v \in \operatorname{son}(u)\}} f_{v} + 1 \]

考虑换根，设 \(g_{u}\) 为以 \(u\) 为根的子树之外的方案数，\(fa\) 为点 \(u\) 的父亲，则有转移

\[g_{u} = g_{fa} (\prod_{\{v \mid v \in \operatorname{son}(fa) \wedge v \neq u\}} f_v + 1) + 1 \]

最终 \(f_u g_u\) 即为点 \(u\) 的答案。

考虑如何快速计算 \(\prod_{\{v \mid v \in \operatorname{son}(fa) \wedge v \neq u\}}\) ，一个直接的想法是从 \(fa\) 的子树中扣去 \(u\) 子树的答案，但由于模数非质且可能有 \(0\)，逆元不一定存在。

考虑维护每个点的所有儿子的 \(f_u+1\) 的前缀积和后缀积，计算时用前一个兄弟的前缀积和后一个兄弟的后缀积计算答案。

代码 
#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,mod;
vector<int>gr[N];
ll f[N],g[N],h[N];
void dfs(int p,int fa){
    f[p]=1;
    for(auto to:gr[p]){
        if(to==fa)continue;
        dfs(to,p),(f[p]*=f[to]+1)%=mod;
    }
    ll res=1;
    for(int i=0;i<(int)gr[p].size();i++){
        int to=gr[p][i];if(to==fa)continue;
        g[to]=res,(res*=f[to]+1)%=mod;
    }
    res=1;
    for(int i=gr[p].size()-1;~i;i--){
        int to=gr[p][i];if(to==fa)continue;
        (g[to]*=res)%=mod,(res*=f[to]+1)%=mod;
    }
}
void redfs(int p,int fa){
    if(p!=1)h[p]=(h[fa]*g[p]+1)%mod;
    for(auto to:gr[p])if(to!=fa)redfs(to,p);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>mod;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        gr[u].push_back(v);gr[v].push_back(u);
    }
    dfs(1,0);
    h[1]=1,redfs(1,0);
    for(int i=1;i<=n;i++)cout<<h[i]*f[i]%mod<<'\n';
    return 0;
}
//coder:Iictiw
//date:24/11/11
//When I wrote a piece of code, her and I knew what it was doing

W - Intervals

数据结构优化 DP。

设 \(f_{i,j}\) 为考虑前 \(i\) 个位置，最近的 \(1\) 在 \(j\) 的最大得分。

对于这类区间带权的题，一种套路化的处理方法是在右端点处更新答案。考虑转移，若在第 \(i\) 位放一个 \(1\)，则有

\[f_{i,i} = \max_{1 \leq j \lt i}(f_{i-1,j} + \sum_{\{k\mid r_k = i \} } a_k) \]

若在第 \(i\) 位放一个 \(0\) ，则有

\[f_{i,j} = f_{i-1,j} + \sum_{\{k\mid l_k \leq j \wedge r_k = i \} } a_k \]

直接做是 \(O(n^2)\) 的。不难发现，对于 \(i\) 相同的 \(f_{i,j}\)，\(\sum_{\{k\mid l_k \leq j \wedge r_k = i \} } a_k\) 是相等的， \(f_i\) 相较于 \(f_{i-1}\) 只有 \(f_{i,i}\) 一个位置在去掉 \(\sum_{\{k\mid l_k \leq j \wedge r_k = i \} } a_k\) 后不同，于是可以让 \(f_i\) 继承 \(f_{i-1}\) 的 \(1\) 至 \(i-1\) 项，然后统一处理 \(\sum_{\{k\mid l_k \leq j \wedge r_k = i \} } a_k\) 对答案的影响，注意到第 \(k\) 个区间影响的 \(f_{i,j}\) 是满足 $ j \in [l_k, r_k]$ 的一段 \(f_{i,j}\) ，于是可以用线段树维护每个区间对答案的影响。

代码 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=2e5+5;
int n,m;
struct node{int l,r,x;}a[N];
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
ll mx[N<<2],tag[N<<2];
inline void push_up(int p){mx[p]=max(mx[ls],mx[rs]);}
inline void make_tag(int p,ll x){mx[p]+=x,tag[p]+=x;}
inline void push_down(int p){
    if(tag[p]){
        make_tag(ls,tag[p]),make_tag(rs,tag[p]);
        tag[p]=0;
    }
}
void update(int p,int l,int r,int L,int R,ll x){
    if(l>=L&&r<=R)return make_tag(p,x);
    if(l>R||r<L)return;
    push_down(p);
    update(ls,l,mid,L,R,x),update(rs,mid+1,r,L,R,x);
    push_up(p);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i].l>>a[i].r>>a[i].x;
    sort(a+1,a+1+m,[&](node x,node y){
        return x.r<y.r;
    });
    for(int i=1,j=1;i<=n;i++){
        update(1,1,n,i,i,max(mx[1],0ll));
        while(j<=m&&a[j].r<=i)update(1,1,n,a[j].l,a[j].r,a[j].x),j++;
    }
    cout<<max(0ll,mx[1])<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/14
//When I wrote a piece of code, her and I knew what it was doing

X - Tower

贪心维护 DP 转移顺序。

Lemma: 必然存在一种最优策略，使得若第 \(i\) 块在第 \(j\) 块下方，则有 \(s_i + w_i \geq s_j + w_j\)。

证明：考虑邻项交换，对于相邻的两个块 \(i\) 与 \(j\)，\(j\) 在 \(i\) 上时，\(i\) 的剩余载量为 \(s_i - w_j\)；\(i\) 在 \(j\) 上时，\(j\) 的剩余载量为 \(s_j - w_i\)。若 \(j\) 在 \(i\) 上不劣于 \(i\) 在 \(j\) 上，则必然有 \(s_i - w_j \geq s_j -w_i\) 。移项可得结论，进而容易推广至任意 \(i,j\)。

因此，可以将所有块以 \(s_i + w_i\) 为关键字降序排序，然后考虑 DP。

设 \(f_{i,j}\) 为放了前 \(i\) 块，还能承载重量为 \(j\) 的最大价值，则若不放第 \(i\) 块，有转移

\[f_{i,j} \gets f_{i-1,j} \]

若放第 \(i\) 块在其他块上，则有转移

\[f_{i,\min(s_i,j - w_i)} \gets f_{i-1,j} + v_i \]

若第 \(i\) 块作为最底部的块，则有转移

\[f_{i,s_i} \gets v_i \]

代码 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=1e4+5;
int n,m;
struct node{int w,s,v;}a[N];
ll f[2][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].w>>a[i].s>>a[i].v,m=max(m,a[i].s);
    sort(a+1,a+1+n,[&](node x,node y){
        return x.w+x.s>y.w+y.s;
    });
    int cur=0;
    f[0][a[1].s]=a[1].v;
    for(int i=2;i<=n;i++){
        cur^=1;
        for(int j=0;j<=m;j++)f[cur][j]=f[cur^1][j];
        f[cur][a[i].s]=max(f[cur][a[i].s],(ll)a[i].v);
        for(int j=0;j<=m;j++)
            if(a[i].w<=j)
                f[cur][min(a[i].s,j-a[i].w)]=max(f[cur][min(a[i].s,j-a[i].w)],f[cur^1][j]+a[i].v);
    }
    ll ans=0;
    for(int i=0;i<=m;i++)ans=max(ans,f[cur][i]);
    cout<<ans<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/14
//When I wrote a piece of code, her and I knew what it was doing

Y - Grid 2

容斥 DP。

直接计算方案数较为困难，考虑容斥，用总方案数减去经过墙的方案数。

一个直接的想法是经过 \(0\) 个墙的方案数 \(-\) 经过 \(1\) 个墙的方案数 \(+\) 经过 \(2\) 个墙的方案数 \(-\) 经过 \(3\) 个墙的方案数……但这种方式难以在低时间复杂度内计算。

考虑将经过墙的方案数不重不漏地表示出来。设 \(f_{i}\) 为在到达第 \(i\) 个墙前不经过其他任何墙的方案数，则可以同样用容斥的方法计算 \(f_i\)，即用到达第 \(i\) 个墙的方案数减去从其他墙到第 \(i\) 个墙的方案数，因此，有转移

\[f_i = {{x_i+y_i-2}\choose{x_i-1}} - \sum_{\{j \mid x_j \leq x_i \wedge y_j \leq y_i\} } f_j {{x_i-x_j+y_i-y_j}\choose{x_i-y_i}} \]

特别地，我们不妨设第 \(n+1\) 个墙位于 \((h,w)\) ，则 \(f_{n+1}\) 即为答案。

代码 
#include<iostream>
#include<cstdio>
#include<algorithm>
#define x first
#define y second
#define mod 1000000007
using namespace std;
using ll=long long;
const int N=2e5+5;
int n,m,k;
pair<int,int>a[N];
ll fct[N],ifct[N];
inline ll qpow(ll a,int p){
    ll ret=1;
    while(p){
        if(p&1)(ret*=a)%=mod;
        (a*=a)%=mod,p>>=1;
    }
    return ret;
}
inline ll C(int n,int m){
    if(n<0||m<0||n<m)return 0;
    return fct[n]*ifct[m]%mod*ifct[n-m]%mod;
}
ll f[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=fct[0]=1;i<N;i++)fct[i]=fct[i-1]*i%mod;
    ifct[N-1]=qpow(fct[N-1],mod-2);
    for(int i=N-2;~i;i--)ifct[i]=ifct[i+1]*(i+1)%mod;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)cin>>a[i].x>>a[i].y;
    a[++k]={n,m};
    sort(a+1,a+1+k);
    for(int i=1;i<=k;i++){
        f[i]=C(a[i].x+a[i].y-2,a[i].x-1);
        for(int j=1;j<i;j++)
            if(a[j].y<=a[i].y)
                f[i]=(f[i]-f[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)%mod+mod)%mod;
    }
    cout<<f[k]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/15
//When I wrote a piece of code, her and I knew what it was doing

Z - Frog 3

斜率优化 DP。

请自行脑补 BGM

设 \(f_i\) 为到点 \(i\) 的最小代价，\(O(n^2)\) 的转移是容易的，即

\[f_i = \min_{1 \leq j \lt i}(f_j + (h_i - h_j)^2 + C) \]

不妨设此时有两个决策点 \(j,k (j \lt k)\)，我们称对于点 \(i\) 来说决策点 \(j\) 优于 \(k\)，当且仅当由 \(j\) 点转移至 \(i\) 点的代价优于由 \(k\) 点转移至 \(i\) 点的代价。若点 \(j\) 优于点 \(k\)，则有

\[f_j + (h_i - h_j)^2 + C \lt f_k + (h_i - h_k)^2 + C \]

化简得

\[f_j + {h_j}^2 - 2 h_i h_j \lt f_k + {h_k}^2 - 2 h_i h_k \]

注意到 \(f_j + {h_j}^2,f_k + {h_k}^2\) 分别只与 \(j,k\) 有关，设 \(g(i) = f_i + {h_i}^2\)，则有

\[g(j) - 2h_ih_j \lt g(k) - 2h_ih_k \]

即

\[g(j) - g(k) \lt 2h_i(h_j - h_k) \]

由于题目保证 h 单调递增，因此 \(h_j - h_k \lt 0\)，于是最终得到

\[\dfrac{g(j) - g(k)}{h_j - h_k} \gt 2h_i \]

如果我们将 \(h_i\) 视为点 \(i\) 的横坐标， \(g(i)\) 视为点 \(i\) 的纵坐标，这个式子就如同求点 \(j\) 与点 \(k\) 的连线的斜率。因此，这种优化方法称为斜率优化。

类似与上式可得，若点 \(j\) 劣于点 \(k\)，则有

\[\dfrac{g(j) - g(k)}{h_j - h_k} \lt 2h_i \]

若点 \(j\) 与点 \(k\) 不相上下，则有

\[\dfrac{g(j) - g(k)}{h_j - h_k} = 2h_i \]

我们不妨再设有 \(j_1,j_2,j_3 (j_1 \lt j_2 \lt j_3 \lt i)\) 三个决策点，思考若

\[\dfrac{g(j_1) - g(j_2)}{h_{j_1} - h_{j_2}} \gt \dfrac{g(j_2) - g(j_3)}{h_{j_2} - h_{j_3}} \]

意味着什么。

分类讨论，设 $slope(i,j) = \dfrac{g(i) - g(j)}{h_{i} - h_{j}} $ 以简化式子。

  • 当 \(2h_i \lt slope(j_2,j_3) \lt slope(j_1,j_2)\) 时：\(j_1\) 优于 \(j_2\)；

  • 当 \(slope(j_2,j_3) \leq 2h_i \leq slope(j_1,j_2)\) 时：\(j_1\) 不劣于 \(j_2\) ， \(j_3\) 不劣于 \(j_2\) ；

  • 当 \(slope(j_2,j_3) \lt slope(j_1,j_2) \lt 2h_i\) 时：\(j_3\) 优于 \(j_2\)。

不难发现，当 \(slope(j_2,j_3) \lt slope(j_1,j_2)\) 时， \(j_2\) 永远不可能成为最优决策点。

在坐标轴上，这表现为直线 \(j_1j_2\) 的斜率大于直线 \(j_2j_3\) 的斜率，此时 \(j_2\) 不可能成为最优决策点。

由此可得，所有可能的最优决策点满足斜率单调递增。

删去所有不可能成为最优决策点的点，不难发现，剩下的点将会构成一个下凸壳：

因此，这种优化方法又称为凸壳优化。

回到本题，考虑如何维护该下凸壳。不难发现本题中，决策点的横坐标（即 \(h_i\)） 单调递增，因此每次只会在原凸壳的末尾加入一个点，可以用单调栈进行维护，以保证斜率单调递增。

查询时，即寻找斜率大于 \(2h_i\) 的最小的位于凸壳上的点，由于凸壳上斜率单调，可以用二分在凸壳上查找出第一个斜率大于 \(2h_i\) 的点，做到 \(O(n\log n)\)。

但在本题中， \(h_i\) 单调递增，因此斜率（即 \(2h_i\)）单调递增，于是最优决策点也单调递增，满足决策单调性。所以，我们可以用单调队列维护最优决策点，每次从队首弹出斜率不大于 \(2h_i\) 的点，从而找到最优决策点，时间复杂度为 \(O(n)\)。

结束了？并没有。

从头开始，回到原转移方程 $ f_i = \min(f_j + {h_i}^2 - 2h_ih_j + {h_j}^2 + C) $ 。将仅与 \(i\) 有关的项和仅与 \(j\) 有关的项分离并去掉 \(min\)，改写为

\[f_j + {h_j}^2 = 2h_ih_j + f_i - {h_i}^2 - C \]

设 \(f_j + {h_j}^2 = y, 2h_i = k, h_j = x, f_i - {h_i}^2 - C = b\)，则转移方程相当于一个一次函数表达式 \(y = kx + b\) 。此时，\((x,y)\) 相当于平面上一个点， \(k\) 相当于直线斜率，\(b\) 表示过点 \((x,y)\) 的斜率为 \(k\) 的直线的截距。注意到 \(k\) 和所有 \((x,y)\) 都是已知的，我们的任务就转化为选择一个点 \(j(j \lt i)\)，使得过点 \((x_j,y_j)\) （即 \((h_j,f_j + {h_j}^2)\)） 的斜率为 \(k_i\)（即 \(2h_i\)）直线截距最小。

不妨假设有一条斜率为 \(k_i\) 的直线自底向上平移，其碰到的第一个点 \((x_j,y_j)\) 即为最优决策点（因为此时截距最小）。

可以看出，所有可能的最优决策点必然位于下凸壳上，每次要找的点也就是凸壳上第一个斜率大于 \(k_i\) 的点。

维护下凸壳和寻找最优决策点，这与上一种做法殊途同归。

代码（二分栈） 
#include<iostream>
#include<cstdio>
using namespace std;
using db=double;
using ll=long long;
const int N=2e5+5;
int n;ll C,a[N];
ll f[N];
int st[N],top;
inline db g(int i){return f[i]+a[i]*a[i];}
inline db slope(int i,int j){return (g(i)-g(j))/(a[i]-a[j]);}
inline int calc(db k){
    int l=1,r=top-1,ret=top;
    while(l<=r){
        int mid=(l+r)>>1;
        if(slope(st[mid],st[mid+1])>=k)r=mid-1,ret=mid;
        else l=mid+1;
    }
    return st[ret];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>C;
    for(int i=1;i<=n;i++)cin>>a[i];
    st[++top]=1;
    for(int i=2;i<=n;i++){
        int j=calc(2*a[i]);
        f[i]=f[j]+(a[i]-a[j])*(a[i]-a[j])+C;
        while(top>1&&slope(st[top-1],st[top])>=slope(st[top],i))top--;
        st[++top]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/18
//When I wrote a piece of code, her and I knew what it was doing
代码（单调队列） 
#include<iostream>
#include<cstdio>
using namespace std;
using db=double;
using ll=long long;
const int N=2e5+5;
int n;ll C,a[N];
ll f[N];
int L=0,R=-1,Q[N];
inline db g(int i){return f[i]+a[i]*a[i];}
inline db slope(int i,int j){return (g(i)-g(j))/(a[i]-a[j]);}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>C;
    for(int i=1;i<=n;i++)cin>>a[i];
    Q[++R]=1;
    for(int i=2;i<=n;i++){
        while(L<R&&slope(Q[L],Q[L+1])<=2*a[i])L++;
        f[i]=f[Q[L]]+(a[i]-a[Q[L]])*(a[i]-a[Q[L]])+C;
        while(L<R&&slope(Q[R-1],Q[R])>=slope(Q[R],i))R--;
        Q[++R]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}
//coder:Iictiw
//date:24/11/18
//When I wrote a piece of code, her and I knew what it was doing

后记

结束了？结束了。

结束了？没结束。

结束了？结束了。

Fumo?fumo。

标签：Educational,再见,int,ll,cin,long,using,include,DP
From： https://www.cnblogs.com/Iictiw/p/18534069

相关文章

  • NFLS DP题单笔记（做不动了未完结）
    录制唱片你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的\(N\)（\(1\leqN\leq20\)）首歌的版权。你打算从中精选一些歌曲，发行\(M\)（\(1\leqM\leq20\)）张CD。每一张CD最多可以容纳\(T\)（\(1\leqT\leq20\)）分钟的音乐，一首歌不能分装在两张CD中。CD数量可以用完，也可以......
  • Linux 下网络套接字(Socket) 与udp和tcp 相关接口
    文章目录1.socket常见API2sockaddr结构体及其子类1.sockaddr结构体定义（基类）2.子类sockaddr_in结构体用于(IPv4)3子类sockaddr_un(Unix域套接字)4.总结画出其结构体3.实现一个简单的tcpEcho服务器和客户端(cpp）3.1客户端3.2服务器3.3测试结果1.socket常......
  • 随机生成LDPC码并类下三角简化编码
    %function[H]=genH(rows,cols)%************设置参数***************rows=8;cols=24;u=[11010001110011011];%**********创建一个1*12的全为零的数组row_flag*******%**********创建一个24*12的全为零的矩阵parity_check**row_flag(1:rows)=0;parity_......
  • 线段树优化DP
    dp，即动态规划中有一类很重要的优化，叫做线段树优化。本文将介绍几种常见的类型及其套路和一些例题。前置知识：线性dp、线段树。权值线段树优化dp此类题目的dp转移通常和数值的大小关系有关，以下将介绍几道权值线段树优化DP题。CF597CSubsequences给定一个\(1\simn......
  • LaTeX教材排版-03：OptionsAndPackages.tex文件说明
    LaTeX教材排版-03：OptionsAndPackages.tex文件说明Latex教材OptionsAndPackages.tex这个文件的作用有两个，一个是自定义了一些文类的选项，根据这些选项做对应的设置，包括调用Book文类等；一个是导入需要用到的宏包。文件内容如下：\newif\ifistwoside\istwosidefalse\DeclareOption{t......
  • 【tokenization分词】WordPiece, Byte-Pair Encoding(BPE), Byte-level BPE(BBPE)的原
    目录前言1、word(词粒度)2、char(字符粒度)3、subword(子词粒度)WordPieceByte-PairEncoding(BPE)Byte-levelBPE(BBPE)总结前言Tokenization（分词）在自然语言处理(NLP)的任务中是最基本的一步，将文本处理成一串tokens用于后续的处理，把文本处理成token有一系列的......
  • DP学习总结
    动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。-----OIWiki例.1-最大子段和分析DP四步⑴定义状态定义\(dp_i\)表示以\(i\)结尾的最大子段和⑵分析答案答案即\({\max}^{i\in[1,n]}_{dp_i}\)⑶分析方程对于每个\(i\)：可以与\([1,i-1......
  • QObject，QMainWindpw，QWidget，QDialog介绍
    QObjectQObject的角色和特点在Qt框架中，QObject是整个对象模型的核心基类，它为Qt对象树和信号-槽机制提供了基础支持。很多Qt的类（包括QWidget、QDialog、QMainWindow）都直接或间接继承自QObject。QObject的核心功能对象树管理（ObjectTree）QObject提供了父子关......
  • 网络编程-002-UDP通信
    1.UDP通信的简单介绍1.1不需要通信握手，无需维持连接，网络带宽需求较小，而实时性要求高1.2包大小有限制，不发大于路径MTU的数据包1.3容易丢包1.4可以实现一对多，多对多2.客户端与服务端=发送端与接收端代码框架收数据方一般都是客户端/接收端3.头文件#include<arpa/ine......
  • 高维前缀和SOSDP
    更新日志概念高维前缀和的名字已经很显然了，不做过多讲解。思路基本形式我们较为熟知的二维前缀和，通常情况下使用了容斥的思想。事实上，更通常的二维前缀和形式往往长下面这样：for(inti=0;i<n;i++){for(intj=0;j<n;j++){for(intk=1;k<n;k++){......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99