关键点#

dp的参数
dp的状态转移方程
初始化
细节部分

P1020 [NOIP1999 提高组] 导弹拦截#

Link

解析#

这道题分为两问，涉及动态规划及贪心思想

Question 1.#

根据题意，第一问求的即为最长不上升子序列。属于非常典型的dp。

$O(N^2)$ 做法#

参数：设 $dp_i$ 表示以 $a_i$ 结尾的最长不上升子序列，最终答案即为 $\max_{1\le i \le n}dp_i$ 。

转移方程： $dp_i=\max_{1\le j<i,a_j\le a_i}(dp_i+1)$

复杂度： $O(N^2)$ 。

$O(n \log n)$ 做法#

当 $n$ 的范围扩大到 $n \leq 10^5$ 时，第一种做法就不够快了，下面给出了一个 $O(n \log n)$ 的做法。

回顾一下之前的状态： $(i, l)$ 。

但这次，我们不是要按照相同的 $i$ 处理状态，而是直接判断合法的 $(i, l)$ 。

再看一下之前的转移： $(j, l - 1) \rightarrow (i, l)$ ，就可以判断某个 $(i, l)$ 是否合法。

初始时 $(1, 1)$ 肯定合法。

那么，只需要找到一个 $l$ 最大的合法的 $(i, l)$ ，就可以得到最终最长不下降子序列的长度了。

摘自OI wiki 最长不下降子序列

根据此思路，可以进行如下分析：

参数： $dp_i$ 为所有的长度为 $i$ 的不下降子序列的末尾元素的最小值， $len$ 为子序列的长度。

做法：当前已知长度为 $1$ ，所以可从 $2$ 到 $n$ 循环，求出前 $i$ 个元素的最长长度，循环过程中不断更新维护 $dp$ 数组及 $len$ 的长度。

如何维护？

考虑每一步的决策，

当 $a_i\le dp_len$ 时，显然可以将其插入序列末尾， $len+=1$ 。

反之，可以将 $dp$ 序列中第一个大于它的元素更新为 $a_i$ 。这一步中可以使用二分解决。

至此，Question 1.解决。

Question 2.#

第二问要求拦截所有导弹所需的最小数量。

考虑贪心#

从第一问来考虑，一套系统所拦截的即为当前的最长不上升子序列，推广考虑，多套系统拦截即为每次删除最长不上升子序列之后重复操作。所以根据Dilworth定理可得，最长上升子序列的长度就是能构成的不上升序列的个数。

所以第二问实际上即为求解最长上升子序列的长度，算法与**Que 1.**基本相同，稍微改动即可。

Code#

1
// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
// #define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
int dp[MaxN],dp2[MaxN];
15

16
inline void Solve()
17
{
18
    int x;
19
  while(cin>>x){
20
        a[++N]=x;
21
    }
22
    dp[1]=a[1];
23
    int len=1;
24
    for(int i=2;i<=N;i++){
25
        if(a[i]<=dp[len]){
26

27
            dp[++len]=a[i];
28
        }
29
        else{
30
            int cnt=upper_bound(dp+1,dp+len+1,a[i],greater<int>())-dp;
31
            dp[cnt]=a[i];
32
        }
33
    }
34
    cout<<len<<endl;
35
    // return;
36
    len=1;
37
    dp2[1]=a[1];
38
    for(int i=2;i<=N;i++){
39
        if(a[i]>dp2[len]){
40
            len++;
41
            dp2[len]=a[i];
42
        }
43
        else{
44
            int cnt=lower_bound(dp2+1,dp2+len+1,a[i])-dp2;
45
            dp2[cnt]=a[i];
46
        }
47
    }
48
    cout<<len<<endl;
49
}
50
signed main()
51
{
52
#ifndef ONLINE_JUDGE
53
    freopen(".in", "r", stdin);
54
    freopen(".out", "w", stdout);
55
#endif
56
    ios::sync_with_stdio(0);
57
    cin.tie(0),cout.tie(0);
58

59
#ifdef MULTI_CASES
60
    cin >> T;
61
    while (T--)
62
#endif
63
       Solve();
64
    //fclose(stdin);
65
    //fclose(stdout);
66
    return 0;
67
}

P1026 [NOIP2001 提高组] 统计单词个数#

解析#

本题求解将一个字符串拆分成 $k$ 个部分，使得每份中包含的单词个数总数最大。

数据很小，考虑 $dp$ 做法。

首先，预处理 $sum_{i,j}$ 数组，表示从 $i$ 到 $j$ 的单词数。从后往前推，可得 $sum_{i,j}=sum_{i+1,j}$ 如果存在从 $a_i$ 开头的单词，则再加一（注意只加一次）。

关于参数，可以从 $answer$ 角度逆向去推，本题所求为分成 $k$ 份以后，包含单词的最大个数。通过简单推理可得，本题 $dp$ 有三个参数，即为：

最大个数
分为 $k$ 份
字符串长度 （这个条件没有明显指出，但十分关键，且在dp类做法中较为常见）

之后推理可得， $dp_{i,j}$ 表示一个长度为 $i$ 的字符串在拆分为 $k$ 份时，最多的单词个数。

考虑状态转移方程，设断点 $r\in [j,i)$ 可以得出： $dp_{i,j}=\max_{j\le r<i}(dp_{i,j},dp_{r,j-1}+sum_{r+1,i})$

大体方向确定后，考虑初始化， $dp_{i,j}=sum_{i,i}+dp_{i-1,i-1}$ $dp_{i,1}=sum_{1,i}$

错误汇总#

RE on #3~#10：数组大小开为 $k$ ，忽略了实际长度应该为 $k\times 20$ 。

Code#

1
// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
// #define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 800;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M, K;
13
int a[MaxN];
14
string sa[10];
15
string s={},s1;
16

17
int sum[MaxN][MaxN];
18
bool check(int l,int r){
19
    string x=s.substr(l,r-l+1);
20
    for(int i=1;i<=K;i++){
21
        if(x.find(sa[i])==0){
22
            return true;
23
        }
24
    }
25
    return false;
26
}
27
void init(){
28
    for(int i=N;i>=1;i--){
29
        for(int j=i;j>=1;j--){
30
            sum[j][i]=sum[j+1][i];
31
            if(check(j,i))sum[j][i]++;
32
        }
33
    }
34
}
35
int dp[MaxN][MaxN];
36
inline void Solve()
37
{
38
  cin>>N>>M;
39
    s+=' ';
40
    for(int i=1;i<=N;i++){
41
        cin>>s1;
42
        s+=s1;
43
    }
44
    N*=20;
45
    cin>>K;
46
    for(int i=1;i<=K;i++){
47
        cin>>sa[i];
48
    }
49
    init();
50
    // dp[0][0]=sum[0][0];
51
    dp[0][0]=0;
52
    for(int i=1;i<=M;i++){
53
        dp[i][i]=dp[i-1][i-1]+sum[i][i];
54
    }
55
    for(int i=1;i<=N;i++){
56
        dp[i][1]=sum[1][i];
57
    }
58
    for(int i=1;i<=N;i++){
59
        for(int j=1;j<=M&&j<i;j++){
60
            for(int r=j;r<i;r++){
61
                dp[i][j]=max(dp[i][j],dp[r][j-1]+sum[r+1][i]);
62
            }
63
        }
64
    }
65
    cout<<dp[N][M];
66
}
67
signed main()
68
{
69
#ifndef ONLINE_JUDGE
70
    freopen(".in", "r", stdin);
71
    freopen(".out", "w", stdout);
72
#endif
73
    ios::sync_with_stdio(0);
74
    cin.tie(0),cout.tie(0);
75

76
#ifdef MULTI_CASES
77
    cin >> T;
78
    while (T--)
79
#endif
80
       Solve();
81
    //fclose(stdin);
82
    //fclose(stdout);
83
    return 0;
84
}

P11187 配对序列#

解析#

根据题意，此题要求出序列中符合 $c_1,c_1,c_2,c_2$ 这种两两相同的最长子序列。

要求子序列最大值，显然我们可以使用 $dp$ 做法。

考虑参数，设 $dp_i$ 表示以 $i$ 为结尾的符合条件的子序列最大值。最终的答案即为 $\max_{1\le i\le n}{dp_i}$

考虑预处理，我们可以先预处理出 $pre_i$ ，表示序列中上一个与 $a_i$ 相同的数的位置。具体实现也十分简单，使用map即可。

不难得出， $pre_i$ 如果不为 $0$ ，则 $dp_i$ 才会有值。又因为每个数字都是成对出现的，所以，只需要找到与这个数相同的上一个数和上一个数的上一个数，求出从上一个数的上一个数的下一位至上一个数的前一位的最大值，这样可以满足 $1\le i<k,s2_i\ne s2_{i+1}$ 的条件。再加上当前的 $2$ 就是 $dp_i$ 的答案。

即 $dp_i=\max_{j=pre_{pre_i}}^{pre_i-1}{dp_j+2}$

关于求 $\max$ 的操作，我们可以使用数据结构优化，比如线段树或者ST表等。

注意如果 $pre_i=0$ 则应该跳过。

Code#

1
// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
// #define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 5e5+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
int pre[MaxN];
15
struct Segment{
16
    struct Point{
17
        int l,r,tag;
18
        int mex;
19
    };
20
    vector<int>a;
21
    vector<Point>t;
22
    Segment(int N){
23
        a.assign(N+10,0);
24
        t.assign(N<<4,{});
25
    }
26
    #define ls p<<1
27
    #define rs p<<1|1
28
    int midd(int p){
29
        return (t[p].l+t[p].r)>>1;
30
    }
31
    void push_up(int p){
32
        t[p].mex=max(t[ls].mex,t[rs].mex);
33
    }
34
    void change(int p,int k,int q){
35
        int l=t[p].l,r=t[p].r;
36
        if(l==r&&l==q){
37
            t[p].mex+=k;
38
            return;
39
        }
40
        int mid=midd(p);
41
        if(q<=mid){
42
            change(ls,k,q);
43
        }
44
        if(mid<q){
45
            change(rs,k,q);
46
        }
47
        push_up(p);
48
    }
49
    void build(int p,int nl,int nr){
50
        t[p].l=nl,t[p].r=nr;
51
        if(nl==nr){
52
            t[p].mex=a[nl];
53
            return;
54
        }
55
        int mid=midd(p);
56
        build(ls,nl,mid);
57
        build(rs,mid+1,nr);
58
        push_up(p);
59
    }
60
    int query(int p,int nl,int nr){
61
        int l=t[p].l,r=t[p].r;
62
        if(nl<=l&&r<=nr){
63
            return t[p].mex;
64
        }
65
        int mid=midd(p);
66
        int ans=0;
67
        if(nl<=mid){
68
            ans=max(ans,query(ls,nl,nr));
69
        }
70
        if(mid<nr){
71
            ans=max(ans,query(rs,nl,nr));
72
        }
73
        return ans;
74
    }
75
};
76
inline void Solve()
77
{
78
    map<int,int>mp;
79
    cin>>N;
80
    Segment Tree(N);
81
    for(int i=1;i<=N;i++){
82
        cin>>a[i];
83
        // Tree.a[i]=a[i];
84
        if(mp[a[i]]==0){
85
            mp[a[i]]=i;
86
            pre[i]=0;
87
        }
88
        else{
89
            pre[i]=mp[a[i]];
90
            mp[a[i]]=i;
91
        }
92
    }
93
    pre[0]=0;
94
    Tree.build(1,1,N);
95
    // Tree.change(1,1,1);
96
    // cout<<1;return;
97
    // vector<int>dp(N+1);
98
    for(int i=1;i<=N;i++){
99
        if(pre[i]==0)
100
            continue;
101
        int maxn=Tree.query(1,pre[pre[i]]+1,pre[i]-1);
102
        // cout<<maxn<<" ";
103
        Tree.change(1,maxn+2,i);
104
    }
105

106
    cout<<Tree.query(1,1,N);
107
}
108
signed main()
109
{
110
#ifndef ONLINE_JUDGE
111
    freopen(".in", "r", stdin);
112
    freopen(".out", "w", stdout);
113
#endif
114
    ios::sync_with_stdio(0);
115
    cin.tie(0),cout.tie(0);
116

117
#ifdef MULTI_CASES
118
    cin >> T;
119
    while (T--)
120
#endif
121
       Solve();
122
    //fclose(stdin);
123
    //fclose(stdout);
124
    return 0;
125
}

P11188 「KDOI-10」商店砍价#

解析#

此题中 $v_i\le 10^5$ 不难得出如果要花费 $n$ 的代价删除剩余的数，数位一定不能大于 $6$ 。

由此可得，设 $dp_{i,j}$ 表示前 $i$ 位中已经删除 $j$ 个数时，删除所有数位的最小代价。

不难得出，每保留单独的一位，代价就会增加 $10^{j-1}\times s_i-v_i$ 。所以我们可以从后往前递推，

可得 $dp_{i,j}=\min(dp_{i,j},dp_{i,j+1}+10^{j-1}\times s_i-v_i)$

显然，我们可以使用滚动数组来优化空间，所以最终的式子为： $dp_j=\min(dp_j,dp_{j+1}+10^{j-1}\times s_i-v_i)$

Code#

1
// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5+100;
10
const int INF = 1e18;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
int binpow(int a,int b){
15
    if(b==0){
16
        return 1;
17
    }
18
    int res=binpow(a,b/2);
19
    if(b%2){
20
        return res*res*a;
21
    }
22
    else{
23
        return res*res;
24
    }
25
}
26
inline void Solve()
27
{
28
  string s;
29
    cin>>s;
30
    for(int i=1;i<=9;i++){
31
        cin>>a[i];
32
    }
33
    int ans=0;
34
    for(int i=0;i<s.size();i++)
35
    {
36
        ans+=a[s[i]-'0'];
37
    }
38
    int sum=ans;
39
    // cout<<ans<<endl;
40
    for(int i=6;i>=1;i--){
41
        vector<int>dp(10);
42
        dp.assign(10,INF);
43
        dp[i]=sum;
44
        for(int j=1;j<=s.size();j++){
45
            for(int ii=1;ii<=i;ii++){
46
                dp[ii]=min(dp[ii],dp[ii+1]+binpow(10,ii-1)*(s[j-1]-'0')-a[s[j-1]-'0']);
47
            }
48
        }
49
        ans=min(ans,dp[1]);
50
        // cout<<dp[1]<<' ';
51
    }
52
    cout<<ans<<endl;
53
}
54
signed main()
55
{
56
#ifndef ONLINE_JUDGE
57
    freopen(".in", "r", stdin);
58
    freopen(".out", "w", stdout);
59
#endif
60
    ios::sync_with_stdio(0);
61
    cin.tie(0),cout.tie(0);
62
    cin>>T;
63
#ifdef MULTI_CASES
64
    cin >> T;
65
    while (T--)
66
#endif
67
       Solve();
68
    //fclose(stdin);
69
    //fclose(stdout);
70
    return 0;
71
}

CF2025D Attribute Checks#

解析#

本题给定了两种属性，在过程中会获得 $m$ 个属性点，以及多次check，求使得通过的check数最多。

考虑 $dp$ 做法，首先是 $dp$ 的状态，设 $dp_{i,j}$ 表示获得 $i$ 个属性点，并将 $j$ 个属性点加在智力，将 $i-j$ 个属性点加在力量上时，能够通过的最多检查数。

考虑状态转移，显然可得：

对于 $a_i(1\le i\le n)$ ，若 $a_i>0$ ： $dp_{cnt,j}=\max_{j=a_i}^{cnt}(dp_{cnt-1,j},dp_{cnt-1,j-1})$ 若 $a_i<0$ ： $dp_{cnt,j}=\max_{j=cnt-\lvert a_i\rvert}^{0}(dp_{cnt,j}+1,dp_{cnt-1,j}+1)$ 若 $a_i=0$ ： $dp_{cnt,j}=dp_{cnt-1,j}(0\le j<cnt)$

考虑优化，可以发现，在cnt更新之后，只要check的值小于等于cnt，只需要将值加一即可。因此我们可以优化掉第一维只保留第二维。对于区间修改，可以使用线段树来实现。

Code#

TLE#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
// #define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e6+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
int dp[5000][5000];
15
inline void Solve()
16
{
17
  cin>>N>>M;
18
    for(int i=1;i<=N;i++){
19
        cin>>a[i];
20
    }
21
    int cnt=0;
22
    for(int i=1;i<=N;i++){
23
        if(a[i]==0){
24
            cnt++;
25
            for(int j=0;j<cnt;j++){
26
                dp[cnt][j]=dp[cnt-1][j];
27
            }
28
        }
29
        else{
30
            if(a[i]>0){
31
                for(int j=a[i];j<=cnt;j++){
32
                    dp[cnt][j]=max(dp[cnt][j]+1,dp[cnt-1][j-1]+1);
33
                }
34
            }
35
            else{
36
                for(int j=cnt-abs(a[i]);j>=0;j--){
37
                    dp[cnt][j]=max(dp[cnt][j]+1,dp[cnt-1][j]+1);
38
                }
39
            }
40
        }
41
    }
42
    int ans=0;
43
    for(int i=0;i<=cnt;i++){
44
        ans=max(ans,dp[cnt][i]);
45
    }
46
    cout<<ans<<endl;
47
}
48
signed main()
49
{
50
#ifndef ONLINE_JUDGE
51
    freopen(".in", "r", stdin);
52
    freopen(".out", "w", stdout);
53
#endif
54
    ios::sync_with_stdio(0);
55
    cin.tie(0),cout.tie(0);
56

57
#ifdef MULTI_CASES
58
    cin >> T;
59
    while (T--)
60
#endif
61
       Solve();
62
    //fclose(stdin);
63
    //fclose(stdout);
64
    return 0;
65
}

AC#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
// #define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e6+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
// int dp[500][5000];
15
struct Segment{
16
    vector<int>a;
17
    struct Point{
18
        int l,r,tag;
19
        int mex;
20
    };
21
    vector<Point>t;
22
    Segment(int N){
23
        a.assign(N,0);
24
        t.assign(N<<2,{});
25
    }
26
    #define ls p<<1
27
    #define rs p<<1|1
28
    int midd(int p){
29
        return (t[p].l+t[p].r)>>1;
30
    }
31
    void push_up(int p){
32
        t[p].mex=max(t[ls].mex,t[rs].mex);
33
    }
34
    void pls(int p,int k){
35
        t[p].tag+=k;
36
        t[p].mex+=k;
37
    }
38
    void push_down(int p){
39
        if(t[p].tag){
40
            pls(ls,t[p].tag);
41
            pls(rs,t[p].tag);
42
            t[p].tag=0;
43
        }
44
    }
45
    void build(int p,int l,int r){
46
        t[p].l=l,t[p].r=r;
47
        if(l==r){
48
            t[p].mex=a[l];
49
            return;
50
        }
51
        build(ls,l,midd(p));
52
        build(rs,midd(p)+1,r);
53
        push_up(p);
54
    }
55
    void dfs(int p,int l,int r){
56
        if(l==r){
57
            a[l]=t[p].mex;
58
            return;
59
        }
60
        int mid=midd(p);
61
        push_down(p);
62
        dfs(ls,l,mid);
63
        dfs(rs,mid+1,r);
64
        push_up(p);
65
    }
66
    void change(int p,int nl,int nr,int k){
67
        int l=t[p].l,r=t[p].r;
68
        if(nl<=l&&r<=nr){
69
            pls(p,k);
70
            return;
71
        }
72
        push_down(p);
73
        int mid=midd(p);
74
        if(nl<=mid){
75
            change(ls,nl,nr,k);
76
        }
77
        if(mid<nr){
78
            change(rs,nl,nr,k);
79
        }
80
        push_up(p);
81
    }
82
    int query_max(int p,int nl,int nr){
83
        int l=t[p].l,r=t[p].r;
84
        if(nl<=l&&r<=nr){
85
            return t[p].mex;
86
        }
87
        int mid=midd(p),ans=0;
88
        push_down(p);
89
        if(nl<=mid){
90
            ans=max(ans,query_max(ls,nl,nr));
91
        }
92
        if(mid<nr){
93
            ans=max(ans,query_max(rs,nl,nr));
94
        }
95
        return ans;
96
    }
97
};
98
inline void Solve()
99
{
100
  cin>>N>>M;
101
    for(int i=1;i<=N;i++){
102
        cin>>a[i];
103
    }
104
    int cnt=0;
105
    Segment Tree(M+10);
106
    Tree.build(1,0,M);
107
    for(int i=1;i<=N;i++){
108
        if(a[i]==0){
109
            cnt++;
110
            Tree.dfs(1,0,M);
111
            for(int j=M;j>=1;j--)
112
                Tree.a[j]=max(Tree.a[j],Tree.a[j-1]);
113
            Tree.build(1,0,M);
114
        }
115
        else{
116
            if(a[i]>0){
117
                if(cnt>=a[i])
118
                    Tree.change(1,a[i],cnt,1);
119
            }
120
            else{
121
                if(cnt>=abs(a[i]))
122
                    Tree.change(1,0,cnt-abs(a[i]),1);
123
            }
124
        }
125

126
    }
127
    // cerr<<cnt;return;
128
    // cout<<1;return;
129
    int ans=0;
130

131
    cout<<Tree.query_max(1,0,cnt)<<endl;
132
}
133
signed main()
134
{
135
#ifndef ONLINE_JUDGE
136
    freopen(".in", "r", stdin);
137
    freopen(".out", "w", stdout);
138
#endif
139
    ios::sync_with_stdio(0);
140
    cin.tie(0),cout.tie(0);
141

142
#ifdef MULTI_CASES
143
    cin >> T;
144
    while (T--)
145
#endif
146
       Solve();
147
    //fclose(stdin);
148
    //fclose(stdout);
149
    return 0;
150
}

P4059 找爸爸（daddy）#

题目分析#

题目要求DNA序列的最大相似程度，考虑 $dp$ 做法，可以得出 $dp_{i,j,k}$ 表示 a序列长度为 $i$ ，b序列长度为 $j$ ，末尾有/无空格（ $k=0$ 无空格， $k=1$ 表示a序列有空格， $k=2$ 表示b序列末尾有空格）时的最大相似程度。

关于空格，对于每段连续空格，相似程度为 $-A-B\times (k-1)$ 因为 $A,B$ 都是正整数，所以其相似程度一定为负数。对于一个空格，会减少 $A$ 点相似度，如果在后面多添加一个空格，则会进一步减少 $B$ 点相似度。

状态转移方程如下：

$dp_{i,j,0}=\max(dp_{i-1,j-1,0},dp_{i-1,j-1,1},dp_{i-1,j-1,2})+a_{s1_i,s2_j}$

$dp_{i,j,1}=\max(dp_{i-1,j,0}-A,dp_{i-1,j,1}-B,dp_{i-1,j,2}-A)$

$dp_{i,j,2}=\max(dp_{i,j-1,0}-A,dp_{i,j-1,1}-A,dp_{i,j-1,2}-B)$

Code#

1
// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
// #define ONLINEJUDGE
7
// #define MULTI_CASES
8
const int MaxN = 2e3 + 100;
9
const int INF = 1e18;
10
int T = 1, N, M;
11
int a[10][10];
12
int dp[MaxN][MaxN][4];
13
int A, B;
14

15
int g(int k)
16
{
17
    return -A - B * (k - 1);
18
}
19
inline void Solve()
20
{
21
    string s1, s2;
22
    cin >> s1 >> s2;
23
    s1 = ' ' + s1;
24
    s2 = ' ' + s2;
25
    map<char, int> mp;
26
    mp['A'] = 1;
27
    mp['T'] = 2;
28
    mp['G'] = 3;
29
    mp['C'] = 4;
30
    for (int i = 1; i <= 4; i++)
31
    {
32
        for (int j = 1; j <= 4; j++)
33
        {
34
            cin >> a[i][j];
35
        }
36
    }
37
    cin >> A >> B;
38
    for (int i = max(s1.size(), s2.size()); i >= 1; i--)
39
    {
40
        dp[0][i][0] = dp[i][0][0] = dp[0][i][2] = dp[i][0][1] = dp[0][i][1] = dp[i][0][2] = -INF;
41
        dp[0][i][1] = dp[i][0][2] = g(i);
42
    }
43
    for (int i = 1; i < s1.size(); i++)
44
    {
45
        for (int j = 1; j < s2.size(); j++)
46
        {
47
            dp[i][j][0] = max({dp[i - 1][j - 1][0], dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]}) + a[mp[s1[i]]][mp[s2[j]]];
48
            dp[i][j][1] = max({dp[i - 1][j][0] - A, dp[i - 1][j][1] - B, dp[i - 1][j][2] - A});
49
            dp[i][j][2] = max({dp[i][j - 1][0] - A, dp[i][j - 1][1] - A, dp[i][j - 1][2] - B});
50
        }
51
    }
52
    cout << max({dp[s1.size() - 1][s2.size() - 1][0], dp[s1.size() - 1][s2.size() - 1][1], dp[s1.size() - 1][s2.size() - 1][2]}) << endl;
53
}
54
signed main()
55
{
56
#ifndef ONLINEJUDGE
57
    freopen("daddy.in", "r", stdin);
58
    freopen("daddy.out", "w", stdout);
59
#endif
60
    ios::sync_with_stdio(0);
61
    cin.tie(0), cout.tie(0);
62

63
#ifdef MULTI_CASES
64
    cin >> T;
65
    while (T--)
66
#endif
67
        Solve();
68
    // fclose(stdin);
69
    // fclose(stdout);
70
    return 0;
71
}

关键点#

P1020 [NOIP1999 提高组] 导弹拦截#

解析#

Question 1.#

O(N2)O(N^2)O(N2) 做法#

O(nlog⁡n)O(n \log n)O(nlogn) 做法#

Question 2.#

考虑贪心#

Code#

P1026 [NOIP2001 提高组] 统计单词个数#

解析#

错误汇总#

Code#

P11187 配对序列#

解析#

Code#

P11188 「KDOI-10」商店砍价#

解析#

Code#

CF2025D Attribute Checks#

解析#

Code#

TLE#

AC#

P4059 找爸爸（daddy）#

题目分析#

Code#

$O(N^2)$ 做法#

$O(n \log n)$ 做法#