dp专题解题报

A - Number of Subsequences

题意是给你一个含有’a’ ‘b’ ‘c’和’?’的字符串,’?’处可任意填入单个’a’ ‘b’或’c’。问所有排列组合中有多少个子序列包含”abc”。

可以列出一个二维的dp数组dp[i][j],表示在i处前有多少个包含a/ab/abc的子序列。

dp[i][0]表示前i个字符中序列总数。每遇到一个’?’,序列数变为三倍。

dp[i][1]的转移只需要根据当前位置若为a,则dp[i][1]累加上序列总数;

dp[i][2]的转移根据当前位置是否为b,为b则转移为dp[i-1][2]+dp[i-1][1];

dp[i][3]的转移根据当前位置是否为c,为c则转移为dp[i-1][3]+dp[i-1][2];

若i处为’?’,则可以表示上述所有情况,并且每种情况递推为当前的三倍加上相应的值。

具体代码如下:

#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

const int maxn=2e5+5,mod=1e9+7;
ll dp[maxn][5];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=" "+s;
    dp[1][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=3;j++) dp[i+1][j]=dp[i][j];
        if(s[i]=='a')
        {
            dp[i+1][1]=(dp[i+1][1]+dp[i][0])%mod;
        }
        else if(s[i]=='b')
        {
            dp[i+1][2]=(dp[i+1][2]+dp[i][1])%mod;
        }
        else if(s[i]=='c')
        {
            dp[i+1][3]=(dp[i+1][3]+dp[i][2])%mod;
        }
        else
        {
            dp[i+1][0]=dp[i][0]*3%mod;
            dp[i+1][1]=(dp[i][1]*3%mod+dp[i][0])%mod;
            dp[i+1][2]=(dp[i][2]*3%mod+dp[i][1])%mod;
            dp[i+1][3]=(dp[i][3]*3%mod+dp[i][2])%mod;
        }
    }
    cout<<dp[n+1][3]<<endl;
    return 0;
}

B - Danger of Mad Snakes

题意为给定n条已知x和y坐标的蛇,并给出它们的攻击力。要求你放置m个捕蛇点(只能以给定蛇为圆心),杀伤力半径范围为r。要求计算每一种方案杀死的蛇的杀伤力总和的平方和。

先单独考虑两条蛇i和j的情况。设两条蛇杀伤力为ai和aj,对答案的贡献可以表示为(…+ai+aj+…)2,化简形式为(ai2+aj2)*w1+(2*ai*aj)*w2

定义以下三种情况:

W:导致i,j同时被杀的捕蛇点的数量

U:导致i被杀但j没被杀的捕蛇点的数量

V:导致j被杀但i没被杀的捕蛇点的数量

一个捕蛇点同时包含i和j的组合数可以计算为c[n][m]-c[n-W][m]。

捕蛇点i和j的方案数为(总方案数-i未被选中的方案数-j未被选中的方案数+ij均未被选中的方案数):c[n-W][m]-c[n-W-U][m]-c[n-W-V][m]+c[n-W-U-V][m]。

两种情况的和即为2*ai*aj的出现次数。

代码如下:

#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

const int maxn=2005,mod=1e9+7;
int n,m,r;
ll c[maxn][maxn],a[maxn],num[maxn];
int x[maxn],y[maxn];
bitset<maxn> b[maxn];

void init()
{
    for(int i=0;i<=n;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
        {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>r;
    init();
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(max(abs(x[i]-x[j]),abs(y[i]-y[j]))<=r)
                b[i][j]=1;
        }
    }
    ll ans=0,w;
    for(int i=1;i<=n;i++)
    {
        w=b[i].count();
        num[i]=(c[n][m]-c[n-w][m]+mod)%mod;
        ans=(ans+num[i]*a[i]%mod*a[i]%mod)%mod;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            w=(b[i]|b[j]).count();
            w=(num[i]+num[j]-c[n][m]+c[n-w][m]+mod)%mod;
            ans=(ans+w*a[i]%mod*a[j]%mod*2%mod)%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

C - Battle Lemmings

给你一个长度为 n 的 01序列,每一次操作你可以交换相邻的两个元素。请计算当最多执行 i 次交换操作,数值均为0且中间夹着至少一个1的最大对数。

设1的个数有gs个,答案x可以表示为:

n*(n-1)/2     所有对数

- gs*(gs-1)/2    (1,1)的对数

- gs*(n-gs)     (1,0)的对数

- ∑li*(li-1)/2    (0,0)且直接没有1的对数

其中li为第i段连续0的长度。要使x最大化,则最后一项取最小值。

设f(i,j,k)为分配好原串的前i个1,第i个1放在新串的j位置,且移动步数为k时,最后一项最小是多少。那么有

f(i,j,k)= min{f(i-1,t,k-|posi-j|)+(j-t-1)*((j-t-2)/2)}

其中posi为原串第i个1的位置。

代码如下:

#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

int a[105],b[105];
ll dp[85][85][8005];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,gs=0,index=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        gs+=a[i];
        if(a[i])
            b[++index]=i;
    }
    ll ans=n*(n-1)/2-gs*(gs-1)/2-gs*(n-gs),x=0;
    mem(dp,INF);
    for(int i=0;i<=index;i++)
    {
        if(i) x+=max(0,(b[i]-b[i-1]-1)*(b[i]-b[i-1]-2)/2);
        dp[i][b[i]][0]=x;
    }
    for(int i=1;i<=index;i++)
    {
        for(int k=1;k<=n;k++)
        {
            for(int j=0;j<k;j++)
            {
                for(int l=0;l<=n*(n-1)/2;l++)
                {
                    dp[i][k][abs(k-b[i])+l]=min(dp[i][k][abs(k-b[i])+l],dp[i-1][j][l]+max(0,(k-j-1)*(k-j-2)/2));
                }
            }
        }
    }
    ll minx=2e18;
    for(int i=0;i<=n*(n-1)/2;i++)
    {
        for(int j=1;j<=n;j++)
        {
            minx=min(minx,dp[index][j][i]+max(0,(n-j)*(n-j-1)/2));
        }
        if(index==0)
            minx=ans;
        cout<<ans-minx<<" ";
    }
    cout<<endl;
    return 0;
}

D - Subsequences of Length Two

给定两个字符串s和t,t的长度固定为2。s中至多可以替换k个字符,求替换后s中子序列与t相同的最大数目。

我们考虑3方的dp。

首先如果t的两个字符相同,则是一个简单的子问题,即求s中有多少个这样的字符,并加上可以更改的最大数目。

如果不相同,我们设dp[i][j][k]表示前i个字符修改了j个后有k个t1

不修改         f[i][j][k] = f[i-1][j][k]

修改为t1

  • 原本就是t1     f[i][j][k] = f[i-1][j][k-1]
  • 否则        f[i][j][k] = f[i-1][j-1][k-1]

修改为t2

  • 原本就是t2     f[i][j][k] = f[i-1][j][k] + k
  • 否则        f[i][j][k] = f[i-1][j-1][k] + k

初始化的话先全部赋值为无穷小,再将f[0][i][0]赋值为0。

代码如下:

#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
ll powmod(ll a,ll b,ll MOD)
{
    ll ans=1;
    while(b)
    {
        if(b%2)
            ans=ans*a%MOD;
        a=a*a%MOD;
        b/=2;
    }
    return ans;
}

int n,k,f[205][205][205];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    string s,t;
    cin>>n>>k;
    cin>>s>>t;
    mem(f,-INF);
    s=' '+s;
    t=' '+t;
    if(t[1]==t[2])
    {
        int ans=0;
        for(int i=1; i<=n; i++)
            if(s[i]==t[1])
                ans++;
        ans=min(ans+k,n);
        cout<<ans*(ans-1)/2<<endl;
    }
    else
    {
        for(int i=0; i<=k; i++)
            f[0][i][0]=0;
        for(int i=1; i<=n; i++)
            for(int j=0; j<=k; j++)
                for(int l=0; l<=i; l++)
                {
                    f[i][j][l]=f[i-1][j][l];
                    if(s[i]==t[1])
                        f[i][j][l]=max(f[i][j][l],f[i-1][j][l-1]);
                    else if(j)
                        f[i][j][l]=max(f[i][j][l],f[i-1][j-1][l-1]);
                    if(s[i]==t[2])
                        f[i][j][l]=max(f[i][j][l],f[i-1][j][l]+l);
                    else if(j)
                        f[i][j][l]=max(f[i][j][l],f[i-1][j-1][l]+l);
                }
        int ans=0;
        for(int i=0;i<=n;i++) ans=max(ans,f[n][k][i]);
        cout<<ans<<endl;
    }
    return 0;
}

小仙女