专题六 动态规划

2025ACM寒假集训

专题六 动态规划

102400226 石华波

Vjudge账号:DustLi

问题一 自然数的拆分问题

问题陈述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

解题思路

上学期啥时候做的了所以语言还是C（）。

如果当前项和之前所选序列之和大于当前项，那就将当前项加入序列中，反之截断序列，由当前项开始。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include<stdio.h>
#include<limits.h>

int main(){
    static int N,A,B,MAX=INT_MIN;
    scanf("%d",&N);
    scanf("%d",&A);
    B=A;
    MAX=B;
    while(--N) {
        scanf("%d",&A);
        B=B+A>A?B+A:A;
        MAX=B>MAX?B:MAX;
    }
    printf("%d",MAX);
    return 0;
}

问题二 采药

问题陈述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

解题思路

0-1背包。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include<iostream>
#include<climits>

using namespace std;

using ll = long long;

int T,M;
int W[101],Val[101],DP[1001];;

int main() {
    cin>>T>>M;
    for(int i=1;i<=M;i++) cin>>W[i]>>Val[i];
    for(int i=1;i<=M;i++) for(int j=T;j>=W[i];j--) DP[j]=max(DP[j],DP[j-W[i]]+Val[i]);
    cout<<DP[T]<<endl;
    return 0;
}

问题三 宝物筛选

问题陈述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 W 的采集车，洞穴里总共有 n 种宝物，每种宝物的价值为 v**i，重量为 w**i，每种宝物有 m**i 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

解题思路

二进制优化的0-1背包。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include<iostream>
#include<climits>

using namespace std;

using ll = long long;

int W,M,cnt=0;
int Wei[100001],Val[100001],DP[100001];;
int Value,Weight,Amount;

int main() {
    cin>>M>>W;
    for(int i=1;i<=M;i++) {
        cin>>Value>>Weight>>Amount;
        int k=1;
        while(Amount>k) {
            Amount-=k;
            Wei[++cnt]=k*Weight;
            Val[cnt]=k*Value;
            k<<=1;
        }
        if(Amount) {
            Wei[++cnt]=Weight*Amount;
            Val[cnt]=Value*Amount;
        }
    }
    for(int i=1;i<=cnt;i++) for(int j=W;j>=Wei[i];j--) DP[j]=max(DP[j],DP[j-Wei[i]]+Val[i]);
    cout<<DP[W]<<endl;
    return 0;
}

问题4 最长公共子序列

问题陈述

给出 1,2,…,n 的两个排列 P1 和 P2 ，求它们的最长公共子序列。

解题思路

把LCS转化为LIS。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<iostream>
#include<climits>

using namespace std;

using ll = long long;

int A[100001], B[100001];
int N;
int DP[100001],Map[100001];
int cnt=0;

int main() {
    cin>>N;
    for(int i=1;i<=N;i++) {
        cin>>A[i];
        Map[A[i]]=i;
        DP[i]=INT_MAX;
    }
    for(int i=1;i<=N;i++) cin>>B[i];
    for(int i=1;i<=N;i++) {
        if(Map[B[i]]>DP[cnt]) DP[++cnt]=Map[B[i]];
        else {
            int L=0,R=cnt,Mid;
            while(L<R) {
                Mid=(L+R)/2;
                if(DP[Mid]>Map[B[i]]) R=Mid;
                else L=Mid+1;
            }
            DP[L]=min(DP[L],Map[B[i]]);
        }
    }
    cout<<cnt;
    return 0;
}

问题五 Kevin and Puzzle

问题陈述

凯文喜欢逻辑谜题。

他和n个同学玩了一个排成一行的游戏。第i个从左边数的人说他们左边有ai个说谎者（不包括他们自己）。

每个同学要么诚实，要么说谎，且有一个限制：没有两个说谎者可以站在一起。诚实的同学总是说真话。说谎者可以说真话或谎言，这意味着他们的陈述被认为是不可靠的。

凯文想要确定不同的游戏配置数量，结果对998244353取模。两个配置被认为不同，如果至少有一个同学在一个配置中是诚实的，而在另一个配置中是说谎者。

解题思路

先将DP数组初始化为0（一开始没发现要初始化用了数组后面懒得改成vector了）,(0,0)的点为1。

处理第i人时，如果说的是真话，那就有ai个骗子，如果是假话，就有a(i-1)+1个骗子（第i个人假话第i-1人必为真话)。

以0表示说真话，1表示说假话。

所以DP[i][1]可以直接等于DP[i-1][0]；

对于DP[i][0]，ai=a(i-1)，那么等于其本身与DP[i-1][0]的和。

如果ai=a(i-2)+1，那么等于其本身与DP[i-2][0]的和（这种情况下i-1说假话）。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<iostream>
#include<climits>
#include<cstring>

using namespace std;

using ll = long long;

const ll Mod=998244353;

int t,n;

void solve() {

}
int main() {
    cin>>t;
    while(t--) {
        cin>>n;
        int Per[n+1];
        Per[0]=0;
        for(int i=1;i<=n;i++) cin>>Per[i];
        ll DP[n+1][2];
        memset(DP,0,sizeof(DP));
        DP[0][0]=1;
        for(int i=1;i<=n;i++) {
            DP[i][1]=DP[i-1][0];
            if(Per[i]==Per[i-1]) DP[i][0]=(DP[i][0]+DP[i-1][0])%Mod;
            if(i>=2&&Per[i]==Per[i-2]+1) DP[i][0]=(DP[i][0]+DP[i-2][0])%Mod;
        }
        cout<<(DP[n][0]+DP[n][1])%Mod<<endl;
    }
    return 0;
}

问题六 World is Mine

问题陈述

Alice 和 Bob 在玩一个游戏。一开始有 nn 个蛋糕，第 ii 个蛋糕的美味值为 aia**i。

Alice 和 Bob 轮流吃蛋糕，Alice 先开始：

  • 在她的回合中，Alice 选择并吃掉任何剩余蛋糕，其美味值严格大于她之前吃过的所有蛋糕中的最大美味值。注意在第一回合中，她可以选择任何蛋糕。
  • 在他的回合中，Bob 选择任何剩余蛋糕并吃掉。

游戏在当前玩家无法吃到合适的蛋糕时结束。设 xx 为Alice吃掉的蛋糕数量。然后，Alice 想要最大化 xx，而Bob 想要最小化 xx。

找出如果两个玩家都以最佳方式玩游戏时，Alice 将吃掉多少个蛋糕。

解题思路

Alice需要递增地吃蛋糕，由于每种蛋糕可能不止出现一次，所以用cnt数组来存储每种蛋糕出现的次数——刚好可以由此递增地访问。

对于同一种蛋糕，Bob需要吃掉所有的这种蛋糕，否则相当于没吃，如果Bob没吃，那么Alice的最优策略必然包含了这种蛋糕。

并且，Bob不能吃超过n/2个蛋糕（两人是轮流吃的）。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

using ll=long long;

int t,n,tas;

int main() {
    cin>>t;
    while (t--) {
        cin>>n;
        vector<int> cnt(n+1);
        for(int i=1;i<=n;i++) {
            cin>>tas;
            cnt[tas]++;
        }
        vector DP(n+1,vector(n+1,LLONG_MAX-1));
        DP[0][0]=0;
        for(int i=1;i<=n;i++) {
            for(int j=0;j<=n>>1;j++) {
                if(cnt[i]==0) DP[i][j]=min(DP[i][j],DP[i-1][j]);
                else {
                    if(j+cnt[i]<=n>>1&&j+cnt[i]<=DP[i-1][j]) DP[i][j+cnt[i]]=min(DP[i][j+cnt[i]],DP[i-1][j]);
                    DP[i][j]=min(DP[i][j],DP[i-1][j]+1);
                }
            }
        }
        ll ans=LLONG_MAX-1;
        for(int i=0;i<=n>>1;i++) ans=min(ans,DP[n][i]);
        cout<<ans<<endl;
    }
    return 0;
}

学习总结

本专题内容主要为动态规划，通过学习，提高了自己的能力。

Licensed under CC BY-NC-SA 4.0
© 2025 - 2026 Dust_Li
2025寒假ACM新生线上集训
使用 Hugo 构建
主题 Stack 由 Jimmy 设计