dp杂题

chenzhiyv · 2025-04-07 14:58:48 · 个人记录

CF404D Minesweeper 1D

1. dp[i][0]表示i-1和i+1都不是雷的情况 =s[i]==0
2. dp[i][1]表示i-1是雷，i+1不是雷的情况 =s[i]==1
3. dp[i][2]表示i-1不是雷，i+1是雷的情况 =s[i]==1
4. dp[i][3]表示i-1是雷，i+1也是雷的情况 =s[i]==2
5. dp[i][4]表示i本身是雷 =s[i]==*

注意dp状态在设计的时候要考虑分类的条件

转移： 当 s[i]==0 时

当 s[i]==1 时

当 s[i]==2 时

当 s[i]==* 时

当 s[i]==? 时，前四种都可以

初值：

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e6+10,mod=1e9+7;
int n;
string s;
int dp[2][5];
signed main()
{
    cin>>s;
    n=s.size();
    s=" "+s;
    dp[0][0]=dp[0][2]=1;
    for(int i=1,o=1;i<=n;i++,o^=1)
    {
        for(int j=0;j<5;j++)
            dp[o][j]=0;
        if(s[i]=='*')
            dp[o][4]=(dp[o^1][2]+dp[o^1][3]+dp[o^1][4])%mod;
        else if(s[i]=='0')
            dp[o][0]=(dp[o^1][0]+dp[o^1][1])%mod;
        else if(s[i]=='1')
        {
            dp[o][1]=dp[o^1][4]%mod;
            dp[o][2]=(dp[o^1][0]+dp[o^1][1])%mod;
        }
        else if(s[i]=='2')
            dp[o][3]=dp[o^1][4]%mod;
        else if(s[i]=='?')
        {
            dp[o][4]=(dp[o^1][2]+dp[o^1][3]+dp[o^1][4])%mod;
            dp[o][0]=(dp[o^1][0]+dp[o^1][1])%mod;
            dp[o][1]=dp[o^1][4]%mod;
            dp[o][2]=(dp[o^1][0]+dp[o^1][1])%mod;
            dp[o][3]=dp[o^1][4]%mod;
        }
    }
    cout<<(dp[n&1][0]+dp[n&1][1]+dp[n&1][4])%mod;
    return 0;
}

CF41D Pawn

容易想到二维dp，这是我们发现不好在k+1的倍数的条件下转移，所以==加维==，并且注意数据范围，每行最多选一个，这一个数最大是9，所有数的总和最多是 900 ，不会炸

答案要判断(n+m-1)(这就是出来的串的长度)的奇偶性，奇数的话在对角线上，偶数在对角线两边

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=500+10,mod=1e9+7;
int dp[2][N][N];
int n,m;
string s[N];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]=" "+s[i];
    }
    if(s[1][1]!=s[n][m])
    {
        cout<<0;
        return 0;
    }
    dp[0][1][n]=1;
    int o=1;
    int flg=(n+m-1)&1;
    for(int i=2;i<=(n+m-1)/2+flg;i++,o^=1)
    {
        memset(dp[o],0,sizeof(dp[o]));
        for(int j=1;j<=min(i,n);j++)
            for(int k=n;k>=max(n-i,j);k--)
                if(s[j][i-j+1]==s[k][n-(i-(m-k))+1])
                    dp[o][j][k]=(dp[o^1][j-1][k+1]+dp[o^1][j][k+1]+dp[o^1][j-1][k]+dp[o^1][j][k])%mod;
    }
    o^=1;//注意
    int ans=0;
    if((n+m-1)&1)
    {
        for(int i=1;i<=n;i++)
        {
            ans+=dp[o][i][i];
            ans%=mod;
        }
        cout<<ans;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            ans+=dp[o][i][i]+dp[o][i][i+1];
            //(i,(n+m-1)/2-i+1),(i+1,(n+m-1)/2-(i+1)+1)
            //(i,(n+m-1)/2-i+1),(i+1,(n+m-1)/2-i)
            ans%=mod;
        }
        cout<<ans;
    }
    return 0;
}

CF467D Fedor and Essay

首先，容易想到可替换的单词连边并对每一个问文章里的单词进行 dfs 的方法，但超时

考虑优化，用 dijkstra 代替 dfs 的过程，就可以了

注意代码细节，如优先队列的重载运算符是反的（如我要长度小的在前边，就要在重载小于的时候写 len1>len2 ），部分量在 dijkstra 时不能改

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e5+10;
string s;
int n,m;
struct dataa
{
    int cnt_c,len,id;
    int cnt_num;
    bool is_artical;
    friend bool operator <(dataa t1,dataa t2)
    {
        if(t1.cnt_c!=t2.cnt_c)
            return t1.cnt_c>t2.cnt_c;
        else
            return t1.len>t2.len;
    }
}c[N];
int cnt_c;
int cnt_id;
unordered_map<string,int> mp;
int h[N],to[N],ne[N],idx;
void add(int u,int v)
{
    to[++idx]=v;
    ne[idx]=h[u];
    h[u]=idx;
}
bool vst[N];
void dijkstra()
{
    priority_queue<dataa> q;
    for(int i=1;i<=cnt_c;i++)
        q.emplace(c[i]);
    while(!q.empty())
    {
        auto u=q.top();
        q.pop();
        for(int i=h[u.id];i;i=ne[i])
        {
            int v=to[i];
            if(c[v].cnt_c>u.cnt_c)
            {
                bool flg=0;
                int tmp=c[v].cnt_num,tmp2=c[v].id;
                if(c[v].is_artical)
                    flg=1;
                c[v]=u;
                c[v].is_artical=flg;
                c[v].cnt_num=tmp;
                c[v].id=tmp2;
                q.emplace(c[v]);
            }
            else if(c[v].cnt_c==u.cnt_c&&c[v].len>u.len)
            {
                bool flg=0;
                int tmp=c[v].cnt_num,tmp2=c[v].id;
                if(c[v].is_artical)
                    flg=1;
                c[v]=u;
                c[v].is_artical=flg;
                c[v].cnt_num=tmp;
                c[v].id=tmp2;
                q.emplace(c[v]);
            }
        }
    }
}
signed main()
{
    cin>>m;
    for(int i=1,cnt=0;i<=m;i++)
    {
        cin>>s;
        cnt=0;
        for(int j=0;j<(signed)s.size();j++)
        {
            if(s[j]>='A'&&s[j]<='Z')
            {
                s[j]=s[j]-'A'+'a';
            }
            if(s[j]=='r')
                cnt++;
        }
        if(mp.find(s)==mp.end())
        {
            cnt_c++;
            c[cnt_c].id=cnt_c;
            c[cnt_c].cnt_c=cnt;
            c[cnt_c].len=s.size();
            c[cnt_c].is_artical=1;
            c[cnt_c].cnt_num=1;
            mp[s]=cnt_c;
        }
        else
            c[mp[s]].cnt_num++;
    }
    cin>>n;
    for(int i=1,cnt=0;i<=n;i++)
    {
        cin>>s;
        cnt=0;
        for(int j=0;j<(signed)s.size();j++)
        {
            if(s[j]>='A'&&s[j]<='Z')
            {
                s[j]=s[j]-'A'+'a';
            }
            if(s[j]=='r')
                cnt++;
        }
        if(mp.find(s)==mp.end())
        {
            cnt_c++;
            c[cnt_c].id=cnt_c;
            c[cnt_c].cnt_c=cnt;
            c[cnt_c].len=s.size();
            c[cnt_c].cnt_num=1;
            mp[s]=cnt_c;
        }
        int id1=mp[s];
        cin>>s;
        cnt=0;
        for(int j=0;j<(signed)s.size();j++)
        {
            if(s[j]>='A'&&s[j]<='Z')
            {
                s[j]=s[j]-'A'+'a';
            }
            if(s[j]=='r')
                cnt++;
        }
        if(mp.find(s)==mp.end())
        {
            cnt_c++;
            c[cnt_c].id=cnt_c;
            c[cnt_c].cnt_c=cnt;
            c[cnt_c].len=s.size();
            c[cnt_c].cnt_num=1;
            mp[s]=cnt_c;
        }
        add(mp[s],id1);
    }
    dijkstra();
    int ans1=0,ans2=0;
    for(int i=1;i<=cnt_c;i++)
    {
        if(!c[i].is_artical)
            continue;
        ans1+=c[i].cnt_c*c[i].cnt_num;
        ans2+=c[i].len*c[i].cnt_num;
    }
    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

CF75D Big Maximum Sum

首先，看到题目就可以想到，最大子段和一定是小数组的最大子段和，或者一个或很多小前缀后缀拼起来，所以设 dp[i][0/1] 表示以第 i 个结尾，不一定选这个对应的小数组的全部/一定选小数组的全部的最大子段和

转移：

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=50+10,M=2.5e5+10,L=5e3+10;
int n,m;
int siz[N];
int small[N][L];
int pre_sum[N][L];
int suf_sum[N][L];
int suf_max[N];
int dp_s[L];
int max_sum[N];
int pre_max[N];
int big[M];
int dp[M][2];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>siz[i];
        for(int j=1;j<=siz[i];j++)
        {
            cin>>small[i][j];
            pre_sum[i][j]=pre_sum[i][j-1]+small[i][j];
        }
        suf_max[i]=-1e9;
        for(int j=siz[i];j>=1;j--)
        {
            suf_sum[i][j]=suf_sum[i][j+1]+small[i][j];
            suf_max[i]=max(suf_sum[i][j],suf_max[i]);
        }
        for(int j=1;j<=siz[i];j++)
            dp_s[j]=-1e9;
        max_sum[i]=pre_max[i]-1e9;
        for(int j=1;j<=siz[i];j++)
        {
            dp_s[j]=max(dp_s[j-1]+small[i][j],small[i][j]);
            max_sum[i]=max(max_sum[i],dp_s[j]);
            pre_max[i]=max(pre_sum[i][j],pre_max[i]);
        }
    }
//  for(int i=1;i<=n;i++)
//      cout<<max_sum[i]<<" ";
//  cout<<endl;
    for(int i=1;i<=m;i++)
        cin>>big[i];
    for(int i=0;i<=m;i++)
        dp[i][0]=dp[i][1]=-1e9;
    for(int i=1;i<=m;i++)
    {
        dp[i][0]=max(dp[i-1][1]+pre_max[big[i]],max_sum[big[i]]);
        dp[i][1]=max(dp[i-1][1]+pre_sum[big[i]][siz[big[i]]],suf_max[big[i]]);
    }
    int ans=-1e9;
    for(int i=1;i<=m;i++)
    {
        ans=max({ans,dp[i][0],dp[i][1]});
//      cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
    }
    cout<<ans;
    return 0;
}

优化后：

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=50+10,M=2.5e5+10,L=5e3+10;
int n,m;
int siz[N];
int small[L];
int pre_sum[N];
int suf_max[N];
int dp_s[2];
int max_sum[N];
int pre_max[N];
int big[M];
int dp[2][2];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>siz[i];
        for(int j=1;j<=siz[i];j++)
        {
            cin>>small[j];
            pre_sum[i]=pre_sum[i]+small[j];
            pre_max[i]=max(pre_sum[i],pre_max[i]);
        }
        suf_max[i]=-1e9;
        int suf_sum=0;
        for(int j=siz[i];j>=1;j--)
        {
            suf_sum=suf_sum+small[j];
            suf_max[i]=max(suf_sum,suf_max[i]);
        }
        dp_s[0]=dp_s[1]=-1e9;
        max_sum[i]=pre_max[i]-1e9;
        for(int j=1,o=1;j<=siz[i];j++,o^=1)
        {
            dp_s[o]=max(dp_s[o^1]+small[j],small[j]);
            max_sum[i]=max(max_sum[i],dp_s[o]);
        }
    }
    for(int i=1;i<=m;i++)
        cin>>big[i];
    dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=-1e9;
    int ans=-1e9;
    for(int i=1,o=1;i<=m;i++,o^=1)
    {
        dp[o][0]=max(dp[o^1][1]+pre_max[big[i]],max_sum[big[i]]);
        dp[o][1]=max(dp[o^1][1]+pre_sum[big[i]],suf_max[big[i]]);
        ans=max({ans,dp[o][0],dp[o][1]});
    }
    cout<<ans;
    return 0;
}

CF894E Ralph and Mushrooms

首先，一个环上可以连续走，所以要一直走到蘑菇全部为0的时候，然后缩点，在新图上dp，因为每条边只能走一遍

同时，我们注意到，一条边单次被减的是 i*(i+1)/2 所以次数一定在 \sqrt n 左右，所以直接正负找5个

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1e6+10;
int n,m;
int h[N],to[N],ne[N],w[N],idx;
int h1[N],to1[N],ne1[N],w1[N],idx1;
struct dataa
{
    int u,v,c;
}edge[N];
void add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add1(int u,int v,int c)
{
    to1[++idx1]=v;
    w1[idx1]=c;
    ne1[idx1]=h1[u];
    h1[u]=idx1;
}
int dfn[N],low[N],time_stamp,scc_cnt,id[N],stk[N],t;
bool in_stk[N];
int sum[N];
int val[N];
void init(int n)
{
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+i*(i+1)/2;
}
int calc(int w)
{
    int tmp=sqrtl(w*2);
    int ans=0;
    for(int i=max(tmp-5,0ll);i<=tmp+5;i++)
    {
        if(i*(i+1)/2>=w)
        {
            ans=i-1;
            break;
        }
    }
    return w*(ans+1)-sum[ans];
}
void tarjin(int u)
{
    dfn[u]=low[u]=++time_stamp;
    stk[++t]=u;
    in_stk[u]=1;
    for(int i=h[u];i;i=ne[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjin(v);
            low[u]=min(low[u],low[v]);
        }
        if(in_stk[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int cur;
        scc_cnt++;
        do{
            cur=stk[t--];
            in_stk[cur]=0;
            id[cur]=scc_cnt;
        }while(cur!=u);
    }
}
int ans[N];
int dfs(int u)
{
    if(ans[u])
        return ans[u];
    for(int i=h1[u];i;i=ne1[i])
    {
        int v=to1[i];
        ans[u]=max(ans[u],w1[i]+dfs(v));
    }
    ans[u]+=val[u];
    return ans[u];
}
int s;
signed main()
{
    cin>>n>>m;
    init(2e4);
    for(int i=1,u,v,c;i<=m;i++)
    {
        cin>>u>>v>>c;
        add(u,v,c);
        edge[idx].u=u;
        edge[idx].v=v;
        edge[idx].c=c;
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjin(i);
    }
    for(int i=1;i<=idx;i++)
    {
        if(id[edge[i].u]==id[edge[i].v])
        {
            val[id[edge[i].u]]+=calc(edge[i].c);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];j;j=ne[j])
        {
            int v=to[j];
            if(id[i]!=id[v])
                add1(id[i],id[v],w[j]);
        }
    }
    cin>>s;
    cout<<dfs(id[s]);
    return 0;
}

CF592D Super M

设 dp[u][0/1] 表示以 u 为根的子树中，回到/不回到u的最小时间，转移：

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1000+10,K=100+10;
int dp[N][K][2][2];
int n,k,m;
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=res*a%k;
        a=a*a%k;
        b>>=1;
    }
    return res%k;
}
int dfs(int cnt,int yushu,bool flg,bool ling)//位数，余数，是否有k的倍数，是否有前导零
{
    if(yushu==0&&!ling)
        flg=1;
    if(!cnt)
        return flg;
    if(dp[cnt][yushu][flg][ling]!=-1)
        return dp[cnt][yushu][flg][ling];
    int res=0;
    if(cnt==1)
    {
        for(int i=1;i<=9;i++)
        {
            res+=dfs(cnt-1,(qpow(10,n-cnt)*i%k+yushu)%k,flg,0),res%=m;
        }
    }
    else
    {
        for(int i=0;i<=9;i++)
        {
            res+=dfs(cnt-1,(qpow(10,n-cnt)*i%k+yushu)%k,flg,ling&&(i==0));
            res%=m;
        }
    }
    dp[cnt][yushu][flg][ling]=res%m;
    return res;
}
signed main()
{
    cin>>n>>k>>m;
    memset(dp,-1,sizeof(dp));
    cout<<dfs(n,0,0,1)<<endl;
    return 0;
}

CF222E Decoding Genome

矩阵优化DP

设 dp[i][j] 表示处理了前 i 位，最后一位是 j 结尾的方案数

转移：

套用矩阵优化

则有(以只有 3 为例)