DP好题集选

56 阅读 0 评论 37 点赞

我是靠谱客的博主瘦瘦哑铃，最近开发中收集的这篇文章主要介绍DP好题集选，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2019年到了,马上又是省赛区域赛的一年了,但是我的dp水平还是堪忧,所以在众多网站(主要codeforce)搜罗一下dp的好题刷一下,并在此发一下解题报告来督促自己....

目录

MemSQL Start[c]UP 3.0 - Round 1 C.Pie Rules
Avito Cool Challenge 2018 C. Colorful Bricks(组合数学+dp)
Codeforces Round #538 (Div. 2) D. Flood Fill
AtCoder Beginner Contest 118 D - Match Matching
Codeforces Round #527 (Div. 3) F. Tree with Maximum Cost(树上dp)
Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!] A. Array Without Local Maximums(计数dp)
[NOIP2018模拟赛] 小P的技能(计数dp+构造二叉树)
Codeforces Global Round 1 D. Jongmah(思维+巧妙DP)
Hello 2019 D. Makoto and a Blackboard(概率dp+积性函数)
Comparing Your Heroes ZOJ 2002(状压dp+拓扑思维)
Codeforces Round #427 (Div. 2) D. Palindromic characteristics(区间dp+hash)
Misunderstood … Missing 2018 Ec-final 西安(二维01背包)
Educational Codeforces Round 60 (Rated for Div. 2) D. Magic Gems(dp+矩阵快速幂优化)
Codeforces Round #548 (Div. 2) D.Steps to On(期望DP+莫比乌斯反演)
浙江师范大学校赛 G.Little Sub and Piggybank(动态规划)
山东省第十届省赛 B.Flipping Game(DP)
Educational Codeforces Round 64 (Rated for Div. 2)(换根dp)
Atcoder AGC 030D Inversion Sum(期望dp)(好题)

MemSQL Start[c]UP 3.0 - Round 1 C.Pie Rules

题意:有n个派,每个派有一个大小,Alice和Bob有一个令牌,谁有令牌可以选择当前派给自己或对方,同时下一回合没有得到派的人将得到令牌,已知每个人都会选择最优的策略,Alice和Bob最终得到的派的体积分别是多少?

题解:因为第一回合是Bob拥有令牌,我们设dp[i]代表第i回合选择的人的最大价值,那么dp[1]就是Bob的答案,然后逆推进行转移就可以了,很不错的dp思维题~~

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=1e9+7;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

int a[maxn],dp[maxn],sum[maxn];
int Sheryang(){

    int n=read;
    for(int i=1;i<=n;i++){
        a[i]=read;
    }
    for(int i=n;i>=1;i--){
        sum[i]=sum[i+1]+a[i];
        dp[i]=max(dp[i+1],sum[i+1]-dp[i+1]+a[i]);
    }

    printf("%d %dn",sum[1]-dp[1],dp[1]);
    return 0;
}

Avito Cool Challenge 2018 C. Colorful Bricks(组合数学+dp)

题意:n个方格m种颜色,要求有k个方格与左边的方格颜色不一样的方案数。

题解:比较简单的计数dp,dp[i][j]为前i个方格有j种不同的方案数,枚举到第i位的时候只有两种状态,和左边一样dp[i][j]+=dp[i-1][j]和左边不一样dp[i][j]+=dp[i-1][j-1]*(m-1)即可~~~

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=998244353;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

ll dp[2005][2005];
void add(ll &x,ll y){
    x+=y;
    if(x>=mod) x-=mod;
}

int Sheryang(){
    int n=read,m=read,K=read;

    dp[1][0]=m;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=min(K,i-1);j++){
            add(dp[i][j],dp[i-1][j]);
            if(j) add(dp[i][j],dp[i-1][j-1]*(m-1)%mod);
            //printf("%d %d = %lldn",i,j,dp[i][j]);
        }
    }

    printf("%lldn",dp[n][K]);
    return 0;
}

Codeforces Round #538 (Div. 2) D. Flood Fill

题意:相邻方块颜色颜色一样则可成为一个联通块,每次可以把一个联通块变为相邻联通块的颜色,最小变换多少次使得所有方块都具有同一颜色。

题解:刚开始的方块左右两边可能和自己是同一颜色,没法直接进行区间dp,所以首先要将相同颜色的联通块压成一块,然后直接进行经典的区间dp就可以了~~(想到压缩也想到区间dp,但是没想到压缩然后区间dp,卡了一段时间才过,蠢死~)

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=1e9+7;
#define pi acos(-1)
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/* keep hungry and keep calm! */

int a[maxn],c[maxn],n,dp[5005][5005];

int dfs(int l,int r){
    if(dp[l][r]!=-1) return dp[l][r];
    int ans=0;
    if(l==r) return 0;
    if(a[l]==a[r]) return ans=dfs(l+1,r-1)+1;
    else ans=min(dfs(l,r-1),dfs(l+1,r))+1;
    dp[l][r]=ans;return ans;
}

int Sheryang(){

    n=read;
    for(int i=1;i<=n;i++){
        c[i]=read;
    }

    a[1]=c[1];
    int cnt=1;

    for(int i=2;i<=n;i++){
        if(a[cnt]==c[i]) continue;
        a[++cnt]=c[i];
    }

    memset(dp,-1,sizeof(dp));
    printf("%dn",dfs(1,cnt));

    return 0;
}

AtCoder Beginner Contest 118 D - Match Matching

题意:有n根火柴,m种数字,数字1,2,3,4,5,6,7,8,9分别需要2,5,5,4,5,6,3,7,6根火柴,要求n根火柴全部都用完且拼成的数字最大,输出这个数字。
题解:简单的完全背包问题,先dp得出拼成的数字的最大位数然后将dp倒回去查找路径,查找路径的过程中可以贪心从最大的数字开始考虑。
Noting:dp数组需要一开始初始化为-1,否则会dp出一个比答案大的值！！！

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=998244353;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

int s[]={0,2,5,5,4,5,6,3,7,6},a[maxn],ans[maxn],n,m,dp[maxn];
int cmp(int a,int b){
    if(s[a]!=s[b]) return s[a]<s[b];
    return a>b;
}

int cmp1(int a,int b){
    return a>b;
}

int Sheryang(){

    n=read,m=read;
    for(int i=0;i<m;i++){
        a[i]=read;
    }
    memset(dp,-1,sizeof(dp));
    dp[0]=1;

    int vis[10]={0};
    for(int i=0;i<m;i++){
        for(int j=s[a[i]];j<=n;j++){
            dp[j]=max(dp[j],dp[j-s[a[i]]]+1);
        }
    }

    sort(a,a+m,cmp1);
    while(n){
        for(int i=0;i<m;i++){
            if(n>=s[a[i]] && dp[n-s[a[i]]]+1==dp[n]){
                putchar(a[i]+'0');
                n=n-s[a[i]];break;
            }
        }
    }

    puts("");
    return 0;
}

Codeforces Round #527 (Div. 3) F. Tree with Maximum Cost(树上dp)

题意:给出一颗有n个节点树以及n个节点的权值,定义一颗以rt为根的树的价值为每一个节点到根的路径长度*节点的权值,你可以以任意节点为根,求树的最大价值.

题解:首先我们先以节点1为根,求出dp[i],表示i节点的子树到i的路径长度*权值,维护一个树上的权值后缀和数组即可转移,然后再进行一次dfs,考虑从u-v 即以u为根的树的价值如何转移到以v为根的树的价值,首先v节点的子树深度都会减少一层,然后u除v的子树以外的子树深度都增加一层,那么转移即可(感觉很清晰经典的树上dp呀)

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=998244353;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

int a[maxn];
ll dp[maxn],sum[maxn];
vector<int>G[maxn];

void dfs1(int u,int fa){
    sum[u]=a[u];
    int sz=G[u].size();
    for(int i=0;i<sz;i++){
        int v=G[u][i];
        if(v==fa) continue;
        dfs1(v,u);
        sum[u]+=sum[v];
        dp[u]+=dp[v]+sum[v];
    }
}

void dfs2(int u,int fa){
    int sz=G[u].size();
    for(int i=0;i<sz;i++){
        int v=G[u][i];
        if(v==fa) continue;
        dp[v]=dp[u]-sum[v]+(sum[1]-sum[v]);
        dfs2(v,u);
    }
}

int Sheryang(){

    int n=read;
    for(int i=1;i<=n;i++){
        a[i]=read;
    }

    for(int i=0;i<n-1;i++){
        int u=read,v=read;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(1,0);
    dfs2(1,0);

    printf("%lldn",*max_element(dp+1,dp+1+n));
    return 0;
}

Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!] A. Array Without Local Maximums(计数dp)

题意:给出一个数组,其中有几项为-1代表没有数字,你可以在里面填数字(1-200),要求满足a[1]<=a[2] && a[i]<=max(a[i-1],a[i+1]) && a[n]>=a[n-1] 的方案数

题解:典型的计数dp,对于第i位你只需要枚举这一位选什么数字以及这一位与i-1位的关系即可,dp[i][j][k]代表第i位选j且与i-1位的关系k的方案数。

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e5+7;
typedef long long ll;
const int mod=998244353;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

ll dp[maxn][205][3],a[maxn]; /// a[i-1]与a[i] < = >
int Sheryang(){

    ll n=read;
    for(int i=1;i<=n;i++){
        a[i]=read;
    }

    for(int i=1;i<=200;i++){
        if(a[1]==-1 || a[1]==i){
            dp[1][i][0]=1;
        }
    }

    for(int i=2;i<=n;i++){
        ll tmp=0; /// a[i-1]<a[i]
        for(int j=1;j<=200;j++){
            if(a[i]==j || a[i]==-1){
                dp[i][j][0]=tmp;
                dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]; ///a[i]==a[i-1]
            }
            tmp+=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2];
            tmp%=mod;
        }

        tmp=0;/// a[i-1]>a[i]
        for(int j=200;j>=1;j--){
            if(a[i]==j || a[i]==-1){
                dp[i][j][2]=tmp;
            }
            tmp+=dp[i-1][j][1]+dp[i-1][j][2];
            tmp%=mod;
        }
    }

    ll ans=0;
    for(int i=1;i<=200;i++){
        ans+=dp[n][i][1]+dp[n][i][2];
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

[NOIP2018模拟赛] 小P的技能(计数dp+构造二叉树)

题意:一颗无限大的二叉树,选择n个节点,要求选择一个节点必先选择父节点,问能选择到第k层节点的方案数。

题解:神仙dp啊！！！一开始的思路dp[i][j]选择j个节点能选到第i层的方案数,但是太难了....实在是不会,看过标称后发现,正解的dp是dp[i][j]选择j个节点不能选到第j层的方案数....经过Tangjz老师的指点,dp[i][j]意思是选择j个节点深度小于i的二叉树的数量,考虑一颗经过根节点的二叉树,根节点左侧树的大小为u,根节点右侧树的大小为v,且层数都小于i,那么删掉根节点后就可以得到两个使用节点分别是u和v且深度小于i-1的二叉树,两颗子树相互不影响那么dp[i][u+v+1]就可以这么转移过来.....

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
using namespace std;
#define Sheryang main
const int maxn=2e5+7;
typedef long long ll;
const int mod=998244353;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

ll f[505][505]; ///f[i][j] 层数小于i点数为j的二叉树的个数
int Sheryang(){
    int n=read,k=read;

    for(int i=1;i<=n+1;i++){
        f[i][0]=1;
    }
    for(int i=2;i<=n+1;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<j;k++){
                f[i][j]+=f[i-1][k]*f[i-1][j-k-1];
                f[i][j]%=mod;
            }
        }
    }

    ll Ans=(f[n+1][n]-f[k][n]+mod)%mod;
    printf("%lldn",Ans);
    return 0;
}

Codeforces Global Round 1 D. Jongmah(思维+巧妙DP)

题意:给出n个在m以内数字,每个数字可以构成[i,i,i] [i-1,i,i+1]的三元组,每个数只能组成一个三元组,问最优组成多少三元组？

题解:这个题有点不太好想,转移什么的真的很巧妙,或许这就是dp的真谛吧....

首先有一个结论,对于一个数x的递增三元组不会超过二个,否则可以转换成三个三张牌相同的三元组,答案是同样优的,对于这个dp我们可以设计三个状态dp[i][j][k]表明考虑数字i时,存在j个以i开头的递增三元组,k个以i做为中间元素的递增三元组.那么便开始考虑从第dp[i-1][k][l] -> dp[i][j][k] 只需要在后面补上几个数字便可以得到转移,同时数字i用了j+k+l个,剩下的可以全部变成[i,i,i]的三元组

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=998244353;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

int f[maxn][3][3],cnt[maxn];
int Sheryang(){
    int n=read,m=read;
    memset(f,-1,sizeof(f));

    for(int i=1;i<=n;i++){
        int x=read;
        cnt[x]++;
    }

    f[0][0][0]=0;
    for(int i=1;i<=m;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                for(int l=0;l<3;l++){
                    if(cnt[i]>=j+k+l){
                        f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+j+(cnt[i]-j-k-l)/3);
                    }
                }
            }
        }
    }

    printf("%dn",f[m][0][0]);
    return 0;
}

Hello 2019 D. Makoto and a Blackboard(概率dp+积性函数)

题意:开始你手里有一个数字n,每一回合它都会等概率的变成它的一个因子,问k回合后这个数字大小的期望.

题解:首先对于这个期望可以猜一下,这是个积性函数....(为啥?我也不知道...要是有大佬知道可以告诉我一下),那么对于积性函数,总期望=每个质因子的的期望的乘积,那么对于每个质因子进行概率dp,dp[i][j]对于某一个质因子来说第i轮时幂次为j的概率是多少,可以枚举第i-1轮的时候的幂次k,转移的概率是1/(k+1),最后再根据概率处理出期望即可.....

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e5+7;
typedef long long ll;
const int mod=1e9+7;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
 
/* keep hungry and keep calm! */
ll dp[(int)1e4+7][62],n,k,inv[62];
 
ll qpow(ll a,ll b){
    ll ans=1;a%=mod;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;b/=2;
    }
    return ans;
}
 
ll solve(ll p,int e){
    dp[0][e]=1;
    for(int i=0;i<e;i++) dp[0][i]=0;
 
    for(ll i=1;i<=k;i++){
        for(int j=0;j<=e;j++){
            dp[i][j]=0;
            for(int k=j;k<=e;k++){
                dp[i][j]=(dp[i][j]+dp[i-1][k]*inv[k+1]%mod)%mod;
            }
        }
    }
    ll tmp=0,t=1;
    for(int i=0;i<=e;i++){
        tmp=(tmp+t*dp[k][i]%mod)%mod;
        t=(t*p)%mod;
    }
    return tmp;
}
 
int Sheryang()
{
    inv[1]=1;
    for(int i=2;i<=60;i++){
        inv[i]=qpow(i,mod-2);
    }
 
    n=read,k=read;
    ll ans=1;
 
    for(ll i=2;i*i<=n;i++){
        int cot=0;
        while(n%i==0) cot++,n/=i;
        if(cot) ans=(ans*solve(i,cot)%mod)%mod;
    }
    if(n>1) ans=(ans*solve(n,1)%mod)%mod;
 
    printf("%lldn",ans);
    return 0;
}

Comparing Your Heroes ZOJ 2002(状压dp+拓扑思维)

题意:给你n对拳皇的名字,代表谁比谁强,要求你根据这个给出现的人物排序,一共有多少种排序的方法？

题解:首先应该能想到一种计数dp,但就没有更深入的想法了....但是我们可以首先将给我们的点对进行连边,这样就变成了一个有向图,我们可以想从前往后进行安排,首先可以安排哪些人？应该是哪些没有入度的点,因为没有人比他们强,那我们延伸一下,若存在一条边u->v,则u一定在v之前安排,那么对于一个点v,只要它的前缀点全部出现在一个排列中,那么就可以安排它,处理这种排练的是状压dp.

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=1e9+7;
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

int dp[maxn],pre[maxn],cnt;
char s[maxn];


int Sheryang()
{
    int n;
    while(~scanf("%d",&n)){
        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        map<string,int>mp;
        cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            int u,v;
            if(!mp.count(s)){
                mp[s]=cnt++;
            }
            u=mp[s];

            scanf("%s",s);
            if(!mp.count(s)){
                mp[s]=cnt++;
            }
            v=mp[s];
            pre[v]|=1<<u;
        }

        dp[0]=1;
        for(int i=0;i<(1<<cnt);i++){if(dp[i])
            for(int j=0;j<cnt;j++){
                if(!(i&(1<<j)) && (i&pre[j])==pre[j]){
                    dp[i|(1<<j)]+=dp[i];
                }
            }
        }

        printf("%dn",dp[(1<<cnt)-1]);
    }
    return 0;
}

Codeforces Round #427 (Div. 2) D. Palindromic characteristics(区间dp+hash)

题意:给你一个字符串,定义k-回文串的含义是对于长度为n的回文字符串,左边长度n/2的子串和右边长度n/2的子串是(k-1)-回文串,输出分别有多少个k-回文串

题解:很容易可以想到一种区间dp的做法,因为对于一个区间只有一个转移,所以总体复杂度n*n,但是分出区间之后还要判断左右两半翻转过来是否相等,这个可以用hash来判断,求一个前缀hash和一个后缀hash,若是回文串,则dp[i][j]表示从i到j最大能形成编号为多少的回文串,dp[i][j]=min(dp[i][i+len/2-1],dp[j-len/2+1][j])+1,转移即可,但是这个题卡hash函数,以后谨慎一点用双hash...

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e6+7;
typedef long long ll;
const int mod=1e9+7;
void Smax(ll &a,ll b){if(a<b) a=b;}
void Smin(ll &a,ll b){if(a>b) a=b;}
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

char s[maxn];
int dp[5002][5002],ans[5005];
ll Has[maxn],p=2333333,Pow[maxn],Hass[maxn];

int judge(int l1,int r1,int l2,int r2){
    ll t1=(Has[r1]-(Has[l1-1]*Pow[r1-l1+1]%mod)+mod)%mod;
    ll t2=(Hass[l2]-(Hass[r2+1]*Pow[r2-l2+1]%mod)+mod)%mod;
    return t1==t2;
}

int Sheryang()
{
    scanf("%s",s+1);
    int n=strlen(s+1);

    Pow[0]=1;
    for(int i=1;i<=n;i++){
        dp[i][i]=1;
        Has[i]=(Has[i-1]*p+s[i])%mod;
        Pow[i]=(Pow[i-1]*p)%mod;
    }
    for(int i=n;i>=1;i--){
        Hass[i]=(Hass[i+1]*p+s[i])%mod;
    }
    ans[1]=n;

    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            if(judge(i,i+len/2-1,j-len/2+1,j)){
                dp[i][j]=min(dp[i][i+len/2-1],dp[j-len/2+1][j])+1;
                ans[dp[i][j]]++;
            }
        }
    }

    for(int i=n-1;i>=1;i--){
        ans[i]+=ans[i+1];
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

Misunderstood … Missing 2018 Ec-final 西安(二维01背包)

题意:初始玩家具有攻击力A和攻击力增幅D都为0,每一回合有三种操作,1.直接对敌方造成A+a[i]点伤害,2.将攻击力增幅提升b[i] 3.将攻击力提升c[i] 回合结束时,攻击力提升当前的攻击力增幅，求n回合后对敌方造成的最大伤害。

题解:可以想到逆推,若最后一回合,那么一定要选择第一个操作,那么若是第i回合,我们讨论第二种操作和第三种操作对于答案的影响,对于第三种种操作,对于伤害会提升后面的攻击次数*c[i]，那么我们dp状态要加上后面的攻击次数,第二种状态,这个还要设计到后面攻击发动的位置,那么我们设后面j次攻击的位置分别为k1,k2...kj,设k=k1+k2+...+kj,那么对于答案的影响是(k1-i+k2-i+...+kj-i)*b[i]=(k-j*i)*c[i],然后还要滚动数组优化一下,同时状态的枚举要参照背包那样,倒着枚举。

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=2e5+7;
typedef long long ll;
#define TYPE ll
const int mod=1e9+7;
void Smax(TYPE &a,TYPE b){if(a<b) a=b;}
void Smin(TYPE &a,TYPE b){if(a>b) a=b;}
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//ar buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<TYPE,TYPE>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/
 
ll a[105],b[105],c[105],dp[2][102][5051];
int Sheryang(){
 
    int T=read;
    while(T--){
 
        memset(dp,0,sizeof(dp));
        int n=read;
        for(int i=1;i<=n;i++){
            a[i]=read;
            b[i]=read;
            c[i]=read;
        }
        dp[n&1][1][n]=a[n];
 
        ll ans=0;
        for(int i=n-1;i>=1;i--){
            for(int j=n-i;j>=1;j--){
                int up=(2*n-j+1)*j/2,down=(2*i+j-1)*j/2;
                for(int k=up;k>=down;k--){
                    int now=i&1,pre=(i+1)&1;
                    Smax(dp[now][j+1][k+i],dp[pre][j][k]+a[i]); //第i次攻击
                    Smax(dp[now][j][k],dp[pre][j][k]+j*c[i]);
                    Smax(dp[now][j][k],dp[pre][j][k]+(k-i*j)*b[i]);
 
                    Smax(ans,dp[now][j+1][k+i]);
                    Smax(ans,dp[now][j][k]);
                }
            }
 
        }
 
        printf("%lldn",ans);
   }
    return 0;
}

Educational Codeforces Round 60 (Rated for Div. 2) D. Magic Gems(dp+矩阵快速幂优化)

题意:有n个空间,有两种数字1和0,他们分别都能占据1个空间,初始你有任意个数字1,数字1可以转化成m个数字0,求占满n个空间的方案数.

题解:状态转移方程其实挺好写的dp[i]代表占据i空间的方案数,dp[i]=dp[i-1]+dp[i-m]占据i个空间可以是占据i-1空间和占据i-m空间枚举过来的,当i<m时,dp[i]=1,但是n特别大1e18,所以考虑优化这个递推式,可以用矩阵快速幂：初始矩阵便是m行1列,dpn]一直到dp[n-m+1],

然后根据上一项的写转移矩阵就可以了。

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
#define TYPE int
const int maxn=1e6+7;
typedef long long ll;
const int mod=1e9+7;
void Smax(TYPE &a,TYPE b){if(a<b) a=b;}
void Smin(TYPE &a,TYPE b){if(a>b) a=b;}
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

struct mat{
    ll m[105][105];
};

int m;
const mat operator *(mat &a,mat &b){
    mat ans;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            ans.m[i][j]=0;
            for(int k=1;k<=m;k++){
                ans.m[i][j]+=a.m[i][k]*b.m[k][j];
                if(ans.m[i][j]>=mod) ans.m[i][j]%=mod;
            }
        }
    }
    return ans;
}

ll qpow(mat a,ll b){
    mat ans;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            ans.m[i][j]=(i==j);
        }
    }

    while(b){
        if(b&1) ans=ans*a;
        a=(a*a);b>>=1;
    }

    ll res=ans.m[1][1];
    for(int i=1;i<=m;i++){
        res+=ans.m[1][i];
        if(res>=mod) res-=mod;
    }
    return res;
}


int Sheryang(){

    ll n=read;
    m=read;

    if(n<m){
        return printf("1"),0;
    }else if(n==m){
        return printf("2"),0;
    }

    mat a;
    memset(a.m,0,sizeof(a.m));
    a.m[1][1]=1;a.m[1][m]=1;
    for(int i=2;i<=m;i++){
        a.m[i][i-1]=1;
    }

    printf("%lldn",qpow(a,n-m));
    return 0;
}

Codeforces Round #548 (Div. 2) D.Steps to On(期望DP+莫比乌斯反演)

题意:有一个为空的队列,每次往队列中随机添加1-m中的一个数,然后求出队列的gcd,若gcd==1则终止,否则继续添加,求最终的队列期望长度。

题解:首先我们可以得到一个期望dp的式子来 $f(i)=1+frac{sum_{j=1}^{j=m}f(gcd(i,j)) }{b}$ 但是这样的复杂度是O( $m^{2}$ ) ,复杂度还是不足以过掉这道题,所以我们需要进行优化:

设 $F(n,x)$ 代表 $1-m$ 中有多少个i使得 $gcd(x,i)=n$ 成立，则 $f(i)=1+ frac{ sum_{d|i}f(d)*F(d,i) }{m}$ 如此,问题便变成了如何解决 $F(n,x)$ ? 易知 $F(n,x)= sum_{i=1}^{m} [gcd(i,x)==n]$ 如此我们便构造一个新函数 $G(n,x)=sum_{n|d}F(d,x)$

$G(n,x)=sum_{i=1}^{m}sum_{n|d}[gcd(i,x)==d]\ =sum_{i=1}^{m} [n|gcd(i,x)] \= sum_{i=1}^{m/n}[1|gcd(i,x/n)] \=m/n*[n|x]$ ,如此根据莫比乌斯反演的公式 $F(n)=sum_{n|d}f(d) Rightarrow f(n)=sum_{n|d} mu(d/n) F(d)$

$F(n,x)=sum_{n|d}mu(d/n)G(d,x) \=sum_{i=1}^{m/n}mu(i)G(n*i) \=sum_{i=1}^{m/n}mu(i)m/(n*i)[(n*i)|x] \sum_{i|(n/x)}mu(i)m/(n*i)$ 代入即可,复杂度O $(mlg^2(m))$ 。

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
#define TYPE int
const int maxn=1e6+7;
typedef long long ll;
const int mod=1e9+7;
void Smax(TYPE &a,TYPE b){if(a<b) a=b;}
void Smin(TYPE &a,TYPE b){if(a>b) a=b;}
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

vector<int>v[maxn];
int pri[maxn],vis[maxn],mu[maxn],n;
ll f[maxn];
void primeall(){
	int cot=0;
	for(int i=2;i<maxn;i++){
		if(vis[i]==0){
			pri[cot++]=i;
			mu[i]=-1;
		}
		for(int j=0;j<cot&&i*pri[j]<maxn;j++){
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}
	}
}

int calc(int x,int y){ /// 1-n gcd(x,i)==y
	int g=x/y,ans=0;
	for(auto p:v[g]){
		ans+=mu[p]*(n/p/y);
	}
	return ans;
}

ll qpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;b/=2;
	}
	return ans;
}

int Sheryang(){
	primeall();
	n=read;
	
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=i){
			v[j].push_back(i);
		}
	}
	
	f[1]=1;mu[1]=1;
	ll inv=qpow(n,mod-2),ans=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<v[i].size()-1;j++){
			int d=v[i][j];
			f[i]=(f[i]+f[d]*calc(i,d)%mod)%mod;
		}
		f[i]=(f[i]*inv+1)%mod;
		f[i]=f[i]*n%mod*qpow(n-calc(i,i),mod-2)%mod;
		ans+=f[i];ans%=mod;
	}
	
	printf("%lldn",ans*inv%mod);
    return 0;
}

浙江师范大学校赛 G.Little Sub and Piggybank(动态规划)

题意:有一个神奇的存钱罐,每天可以往里面存任意实数的钱,但是后一天存的钱不能比前一天存的钱多,每天都有价值为v的商品,只有当存钱罐里的钱等于商品的价值才可以购买,购买后将得到快乐值,求最大的快乐值。

题解:可以设计dp[i][j]代表最后买的商品是i倒数第二件买的商品是j所能得到的最大快乐值,那么状态转移便是dp[i][j] = max(dp[j][k]) + v[i]; 如何直接转移复杂度是O(n^3) 但是这个max(dp[j][k])其实是可以在之前的转移中去维护的,定义mx[i][j] = max(dp[i][j]~dp[i][i]) ,则状态转移便可以改写成 dp[i][j] = mx[j][k] + v[i] k是任意的吗？肯定不是的,我们便要找到最小的k,又因为之前的条件,后一天存的钱不能比前一天多, $frac{w[i]]}{i-j} leq frac{w[j]}{j-k}$ 于是化简得到 $k geq j-frac{w[j]}{w[i]}*(i-j)$

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=2e5+7;
typedef long long ll;
const int mod=1e9+7;
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/
  
int w[maxn],v[maxn],dp[2005][2005],mx[2005][2005];

int Sheryang(){
    
    int n=read;
    
    for(int i=1;i<=n;i++){
    	w[i] = read;
	}
	for(int i=1;i<=n;i++){
		v[i] = read;
	}
	
	// mx[i][j]  dp[i][j] - dp[i][i-1]的最大值 
	// dp[i][j] = max(dp[j][k]) + v[i] 
	for(int i=1;i<=n;i++){
		
		dp[i][0] = v[i];
		for(int j=1;j<i;j++){
			int k = (w[i]==0)? 0:max((int)ceil( j*1.0-1.0*w[j]/w[i]*(i-j) ),0);
			if(mx[j][k]) dp[i][j] = mx[j][k] + v[i];
		}
		
		for(int j=i-1;j>=0;j--){
			mx[i][j] = max(mx[i][j+1],dp[i][j]);
		}
	}
	
	int ans = 0;
	for(int i=1;i<=n;i++){
		ans = max(ans,mx[i][0]);
	}
	
	printf("%dn",ans);
    return 0;
}

山东省第十届省赛 B.Flipping Game(DP)

题意:给你长度为n的01串的初始状态和最终状态,可改变m轮,每轮改变k个字符的状态 0->1 1->0,输出从初始状态变到末尾状态的方案数(n,m,j<=100).

题解:比赛的时候死活没想到这个咋dp....状态想不到,赛后看到别人代码恍然大悟,其实是个蛮简单的dp, $dp[i][j]$ 代表第i轮s和t有j个相同字符的方案数,如此状态转移便可以枚举之前的状态,然后枚举将多少个1变成0,然后组合数计算一下便可以了.....

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=5e4+7;
typedef long long ll;
const int mod=998244353;
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/


ll dp[105][105],C[105][105];
char s[105],t[105];
int Sheryang(){
	C[0][0] = 1;
    for(int i=0;i<=100;i++){ 
    	for(int j=0;j<=i;j++){
    		if(i==j || !j){
    			C[i][j] = 1;
			}else{
				C[i][j] = C[i-1][j] + C[i-1][j-1];
			}
    		if(C[i][j]>=mod){
    			C[i][j] -= mod;
			}
		}
	}
	int T = read;
	while(T--){
		int n=read,m=read,K=read;
		
		for(int i=0;i<=m;i++){
			for(int j=0;j<=n;j++){
				dp[i][j] = 0;
			}
		}
		
		scanf("%s%s",s+1,t+1);
		
		int num = 0;
		for(int i=1;s[i];i++){
			if(s[i] == t[i]){
				num ++;
			}
		}
		dp[0][num] = 1; //初始有num位相同 
		
		for(int i=0;i<m;i++){
			for(int j=0;j<=n;j++){ //枚举有多少个 0 
				if(dp[i][j]){
					int limit = min(j,K);
					for(int k=0;k<=limit;k++){ // k位相同的翻成不同的 K-k位不同翻成相同 
						dp[i+1][j+(K-k)-k] += dp[i][j]*C[j][k]%mod*C[n-j][K-k]%mod;
						dp[i+1][j+(K-k)-k] %= mod;
					}
				}
			}
		}
		
		printf("%lldn",dp[m][n]);
	}
    return 0;
}

Educational Codeforces Round 64 (Rated for Div. 2)(换根dp)

题意:给你一颗n个节点的树,边权只有0和1,在树上选择两个节点u,v,若u到v的边权是不递减的,则是合法的路径,求一共有多少的合法路径?

题解:dp[u][0/1/2/3/4]从u到底,全0 先0后1 先1后0 全1的路径有多少,然后就可以枚举一条边进行换根dp,状态转移有点多,需要仔细考虑一下所有的可行状态,同时若u->v路径上的权值是不变的,那么答案就要*2,同时注意一下状态是从上到下的就可以了......

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=2e5+7;
typedef long long ll;
const int mod=1e9+7;
//#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

int nxt[maxn<<2],head[maxn],to[maxn<<2],w[maxn<<2],cnt;
void add(int u,int v,int vol){
	nxt[++cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
	w[cnt] = vol;
}
ll dp[maxn][5],Ans;
// 00 01 10 11

void dfs(int u,int fa){
	ll tmp = 0;
	for(int i=head[u];~i;i=nxt[i]){
		int v = to[i];
		int vol = w[i];
		if(v == fa){
			continue;
		}
		dfs(v,u);
		if(vol){
			tmp += dp[u][0]*(dp[v][3]+1);
			tmp += dp[u][2]*(dp[v][3]+1);
			tmp += dp[u][3]*(dp[v][0]+dp[v][2]+2*dp[v][3]+2);
			tmp += dp[v][0]+dp[v][2]+2*dp[v][3]+2;
			
			dp[u][3] += dp[v][3] + 1;
			dp[u][2] += dp[v][0] + dp[v][2];
		}else{
			tmp += dp[u][0]*(2*dp[v][0] + dp[v][1] + dp[v][3] + 2);
			tmp += dp[u][1]*(dp[v][0]+1);
			tmp += dp[u][3]*(dp[v][0]+1);
			tmp += 2*dp[v][0] + dp[v][1] + dp[v][3]+2;
			
			dp[u][0] += dp[v][0]+1;
			dp[u][1] += dp[v][1] + dp[v][3];
		}
	}
	Ans += tmp;
}

int Sheryang(){
      
   	int n = read;
	memset(head,-1,sizeof head);
	
	for(int i=1;i<n;i++){
		int u = read, v = read,vol = read;
		add(u,v,vol);
		add(v,u,vol);
	}
	
	dfs(1,0);
	
	printf("%lldn",Ans);
    return 0;
}

Atcoder AGC 030D Inversion Sum(期望dp)(好题)

题意:有一个序列 $a1,a2,a3....an$ ,有Q次操作,每次给出x和y,可以选择是否交换x和y位置上的数字,共有 $2^Q$ 种可能,计算所有可能的逆序数的和。 $n,Q <= 3000$

题解: $dp[i][j][k]$ 代表前i轮 $a[j]<a[k]$ 的期望次数,若这轮选择交换 $dp[i][x][y] += dp[i-1][y][x]$ 不交换的话 $dp[i][x][y] += dp[i-1][x][y]$ 其他n个位置同理,最后乘上总方案数就可以了。

#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=2e5+7;
typedef long long ll;
const int mod=1e9+7;
///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
#define IO cin.tie(0),ios::sync_with_stdio(false);
#define pi acos(-1)
#define PII pair<ll,ll>
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
#define read read()
/** keep hungry and keep calm! **/

ll qpow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1) ans = ans*a%mod;
		a=a*a%mod; b/=2;
	}
	return ans;
}

ll dp[3005][3005];
int a[3005];
int Sheryang(){
    
	int n = read , Q = read;
	ll tot = qpow(2,Q);
	ll inv = qpow(2,mod-2);
	
	for(int i=1;i<=n;i++){
		a[i] = read;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j] = (a[i]<a[j]);
		}
	}
	
	// dp[x][y] a[x]<a[y] 的期望 
	while(Q--){
		int x = read,y = read;
		dp[x][y] = dp[y][x] = (dp[x][y]+dp[y][x])*inv%mod;
		for(int i=1;i<=n;i++){
			if(i!=x&&i!=y){
				dp[i][x] = dp[i][y] = (dp[i][x]+dp[i][y])*inv%mod;
				dp[x][i] = dp[y][i] = (dp[x][i]+dp[y][i])*inv%mod;
			}
		}
	}
	
	ll ans = 0;
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			ans += dp[i][j];
			if(ans>=mod) ans -= mod;
		}
	}
	ans = ans*tot%mod;
	
	printf("%lldn",ans);
    return 0;
}

最后

以上就是瘦瘦哑铃为你收集整理的DP好题集选的全部内容，希望文章能够帮你解决DP好题集选所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：期望概率
浏览次数：56 次浏览
发布日期：2023-09-24 03:30:14
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzocfx_12__7__6_0.html

DP好题集选

概述

MemSQL Start[c]UP 3.0 - Round 1 C.Pie Rules

Avito Cool Challenge 2018 C. Colorful Bricks(组合数学+dp)

Codeforces Round #538 (Div. 2) D. Flood Fill

AtCoder Beginner Contest 118 D - Match Matching

Codeforces Round #527 (Div. 3) F. Tree with Maximum Cost(树上dp)

Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!] A. Array Without Local Maximums(计数dp)

[NOIP2018模拟赛] 小P的技能(计数dp+构造二叉树)

Codeforces Global Round 1 D. Jongmah(思维+巧妙DP)

Hello 2019 D. Makoto and a Blackboard(概率dp+积性函数)

Comparing Your Heroes ZOJ 2002(状压dp+拓扑思维)

Codeforces Round #427 (Div. 2) D. Palindromic characteristics(区间dp+hash)

Misunderstood … Missing 2018 Ec-final 西安(二维01背包)

Educational Codeforces Round 60 (Rated for Div. 2) D. Magic Gems(dp+矩阵快速幂优化)

Codeforces Round #548 (Div. 2) D.Steps to On(期望DP+莫比乌斯反演)

浙江师范大学校赛 G.Little Sub and Piggybank(动态规划)

山东省第十届省赛 B.Flipping Game(DP)

Educational Codeforces Round 64 (Rated for Div. 2)(换根dp)

Atcoder AGC 030D Inversion Sum(期望dp)(好题)

最后

评论列表共有 0 条评论

发表评论取消回复

DP好题集选

概述

MemSQL Start[c]UP 3.0 - Round 1 C.Pie Rules

Avito Cool Challenge 2018 C. Colorful Bricks(组合数学+dp)

Codeforces Round #538 (Div. 2) D. Flood Fill

AtCoder Beginner Contest 118 D - Match Matching

Codeforces Round #527 (Div. 3) F. Tree with Maximum Cost(树上dp)

Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!] A. Array Without Local Maximums(计数dp)

[NOIP2018模拟赛] 小P的技能(计数dp+构造二叉树)

Codeforces Global Round 1 D. Jongmah(思维+巧妙DP)

Hello 2019 D. Makoto and a Blackboard(概率dp+积性函数)

Comparing Your Heroes ZOJ 2002(状压dp+拓扑思维)

Codeforces Round #427 (Div. 2) D. Palindromic characteristics(区间dp+hash)

Misunderstood … Missing 2018 Ec-final 西安(二维01背包)

Educational Codeforces Round 60 (Rated for Div. 2) D. Magic Gems(dp+矩阵快速幂优化)

Codeforces Round #548 (Div. 2) D.Steps to On(期望DP+莫比乌斯反演)

浙江师范大学校赛 G.Little Sub and Piggybank(动态规划)

山东省第十届省赛 B.Flipping Game(DP)

Educational Codeforces Round 64 (Rated for Div. 2)(换根dp)

Atcoder AGC 030D Inversion Sum(期望dp)(好题)

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复