动态规划合集

• 子序列的和
  题目：有一个正整数 N 和一个序列 {1，2，3，…，N }，问有多少个子序列的和恰为 N。

输入：
若干行，每行一个整数，第 i 行为 Ni， Ni 与题中 N 的含义一致
1 ≤ Ni ≤ 100
当i ≠ j 时，Ni ≠ Nj

输出：
若干行，每行一个整数

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int dp[N][N];//dp[i][j]表示从1到i中子序列的和恰好为j的数量
int n;
int main()
{
    dp[1][1]=1;
    for(int i=2;i<=N;i++){
        dp[i][1]=1;
        dp[1][i]=0;
        for(int j=2;j<=N;j++){
            if(j>(1+i)*i/2) dp[i][j]=0;
            else if(j>i) dp[i][j]=dp[i-1][j-i]+dp[i-1][j];
            else dp[i][j]=dp[j-1][j]+1;
        }
    }
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",dp[n][n]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 三棵树
  题目：A城市有一条长直街道，为了绿化环境和净化空气，市政府决定沿着街道种植一排树。园林部门得到指令后，初步规划出 n（n ≥ 5）个种树的位置，编号1到n。
  并且每个位置都有一个美观度 Ai，如果在这里种树就可以得到这 Ai 的美观度。
  但由于 A 城市土壤肥力欠佳，两棵树决不能种在相邻的位置（ i 号位置和 i+1 号位置叫相邻位置）。
  最终市政府给园林部门提供了 3 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。

输入
包含多个测试实例，对于每个测试实例
占一行，第一个数是整数n，接下去为n个整数 Ai
测试实例数量不超过 10 个

输出
每个测试实例一行一个整数，表示最佳的植树方案可以得到的美观度

#include<bits/stdc++.h>
using namespace std;
const int N=105,inf=0xc0c0c0c0;//美观度可能为负数，所以初始化为负无穷
int dp[N][4];//dp[i][j]表示第i个位置上种了j棵树的美观度
//dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+a[i])
int n,a[N];
int main()
{
    while(scanf("%d",&n)!=EOF){
        memset(dp,inf,sizeof(dp));
        for(int i=1;i<=n;i++){
            cin>>a[i];
            dp[i][0]=0;
        }
        dp[0][0]=0;
        dp[1][1]=a[1];
        for(int i=2;i<=n;i++){
            for(int j=1;j<=3;j++){
                dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+a[i]);
            }
        }
        printf("%d\n",dp[n][3]);
    }
    return 0;
}
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

• 买股票的最佳时机1
  题目：长度 N 的整数序列 { Pi } 是一只股票在一个有 N 个交易日的时间段内的价格（Pi 是第 i 天的价格）。若在此期间最多只允许买卖各 1 次，问获利最大是多少？
  规则： 初始时刻不持有股票，每次交易只能买或卖 1 股

输入
第一行一个整数 N，表示有 N 个交易日
第二行 N 个整数 Pi，表示 N 天的股票价格

输出
一行一个整数，表示最大利润

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int p[N],dp[N],p2[N];//p2[i]表示买的价格
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    p2[1]=p[1];
    for(int i=2;i<=n;i++) p2[i]=min(p[i],p2[i-1]);
    dp[1]=0;
    for(int i=2;i<=n;i++) dp[i]=max(dp[i-1],p[i]-p2[i-1]);
    printf("%d",dp[n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 买股票的最佳时机2
  题目：长度 N 的整数序列 { Pi } 是一只股票在一个有 N 个交易日的时间段内的价格（Pi 是第 i 天的价格）。若在此期间最多只允许买卖各 2 次，问获利最大是多少？
  买卖规则：
  1、每次交易只能买卖1股
  2、同一个交易日可以多次买卖
  3、初始时刻不持有股票，任意时刻持股不能超过1股

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,p[N],p1[N],p2[N],dp[N];
//p1[n]:从1～n天内进行不多于一次完整交易的最大利润
//p2[n]:从n～N天内进行不多于一次完整交易的最大利润
int main()
{
   // memset(dp,0,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    p1[1]=0;
    p2[n]=0;
    for(int i=2,j=p[1];i<=n;i++){
        if(j>p[i]) j=p[i];
        p1[i]=max(p1[i-1],p[i]-j);
    }
    for(int i=n-1,j=p[n];i>=1;i--){
        if(j<p[i]) j=p[i];
        p2[i]=max(p2[i+1],j-p[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,p1[i]+p2[i]);
    }
    printf("%d",ans);
    return 0;
}
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

• 波动数列
  题目：观察这个数列：1，3，0，2，-1，1，-2，…
  这个数列中后一项总是比前一项增加 2 或者减少 3。
  栋栋对这种数列很好奇，他想知道长度为 n、和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？

输入
一行四个整数n、s、a、b，含义如前面说述。

输出
一行一个整数，表示满足条件的方案数
由于这个数很大，请输出方案数除以100000007的余数。

#include<bits/stdc++.h>
using namespace std;
const int N=1005,mode=100000007;
int n,s,a,b;
int dp[N][N];//dp[i][j]表示长度为i余数为j的方案数
int main()
{
    scanf("%d%d%d%d",&n,&s,&a,&b);
    dp[0][0]=1;//0个数余数为0的方案数为1
    for(int i=1;i<n;i++){
        for(int j=0;j<n;j++){
            dp[i][j]=(dp[i-1][((j-(n-i)*a)%n+n)%n]+dp[i-1][(j+(n-i)*b)%n])%mode;
        }
    }
    printf("%d",dp[n-1][s%n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 种树
  题目：A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。
  并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。
  最终市政府给园林部门提供了m 棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上，给出无解信息。

输入
输入的第一行包含两个正整数n、m
第二行n个整数Ai

输出
一个整数，表示最佳的植树方案可以得到的美观度。
如果无解输出“Error!”，不包含引号

#include<bits/stdc++.h>
using namespace std;
const int N=1005,inf=0xc0c0c0c0;
int n,m,a[N];
int dp[N][N];
int main()
{
    cin>>n>>m;
    int x,y;
    memset(dp,inf,sizeof(dp));
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if((n==1&&m>1)||(n>1&&n<=2*m-1)){
        printf("Error!");
        return 0;
    }
    for(int i=1;i<=m-1;i++) dp[1][i]=dp[2][i]=inf;
    for(int i=3;i<n;i++){
        for(int j=1;j<m;j++)
            dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+a[i]);
    }
    //x=dp[n-1][m-1]+a[1];
    dp[0][0]=0;
    dp[1][0]=0;
    for(int i=1;i<=m;i++) dp[0][i]=dp[1][i]=inf;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++)
            dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+a[i]);
    }
    //y=dp[n][m];
    printf("%d",max(dp[n-1][m-1]+a[1],dp[n][m]));
    return 0;
}
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

• 房屋染色1
  题目：N 个房子在一列直线上，现在需要给所有房子染色，颜色有红色、蓝色和绿色三种，染色费用和房子与颜色都有关。
  若相邻的房屋颜色不能相同，那么所有可行的染色方案中费用最小的方案的费用是多少？

输入
第一行一个整数 N，表示房子数量
接下去 N 行，每行 3 个整数 ri、bi 和 gi，表示房子 i 染成红色、蓝色和绿色的费用

输出
一个整数，表示最少费用

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5,maxs=0x3f3f3f3f;
int n,r[N],b[N],g[N],a[N][4];
int dp[N][4];//1表示红色，2表示蓝色，3表示绿色
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=3;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++){
        dp[i][1]=min(dp[i-1][2],dp[i-1][3])+a[i][1];
        dp[i][2]=min(dp[i-1][1],dp[i-1][3])+a[i][2];
        dp[i][3]=min(dp[i-1][1],dp[i-1][2])+a[i][3];
    }
    int s=maxs;
    for(int i=1;i<=3;i++){
        s=min(s,dp[n][i]);
    }
    printf("%d",s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 房屋染色2
  题目：N 个房子在一列直线上，现在需要给所有房子染色，颜色有 K 种，染色费用和房子与颜色都有关。
  若相邻的房屋颜色不能相同，那么所有可行的染色方案中费用最小的方案的费用是多少？

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5,M=505,inf=0x3f3f3f3f;
int n,k;
int c[N][M],dp[N][M];//dp[i][j]表示把第i个房子染成第j个颜色的费用
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            scanf("%d",&c[i][j]);
        }
    }
    memset(dp,inf,sizeof(dp));
    for(int i=1;i<=k;i++) dp[1][i]=c[1][i];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++){
            for(int l=1;l<=k;l++){
                if(l!=j) dp[i][j]=min(dp[i][j],dp[i-1][l]+c[i][j]);
            }
        }
    }
    //dp[n][k]表示把第n个房子染成第k个颜色的费用，不一定总的费用最小，所以要比较把第n个染成1，2，……，k颜色，选出一个最小费用
    int s=inf;
    for(int i=1;i<=k;i++){
        s=min(s,dp[n][i]);
    }
    printf("%d",s);
    return 0;
}
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

• 最大和区间
  题目：设 { Ai } 是长度为 N 的整数序列，SL,R = AL + AL+1 + …… + AR，求 Mk = max(S1,k，S2,k，S3,k，……，Sk,k)。

输入
包含多个测试用例，每个测试用例占三行，对于每个测试用例
第一行两个整数 N、Q，表示序列长度和查询次数
第二行 N 个整数 Ai，表示序列
第三行 Q 个整数 ki，表示查询 Mki

输出
每个测试用例一行，第 i 行 若干个整数，表示第 i 个测试用例的Q个查询结果

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,maxs=0x3f3f3f3f;
int n,q,a[N],k;
int dp[N];
int main()
{
    while(scanf("%d%d",&n,&q)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        dp[1]=a[1];
        for(int i=2;i<=n;i++) dp[i]=max(a[i],dp[i-1]+a[i]);
        for(int i=1;i<q;i++){
            scanf("%d",&k);
            dp[k]=max(a[k],dp[k-1]+a[k]);
            printf("%d ",dp[k]);
        }
        cin>>k;
        dp[k]=max(a[k],dp[k-1]+a[k]);
        printf("%d\n",dp[k]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 最小值
  题目：有一个长度为 N 的整数序列 { Ai }。问：去掉元素 Ak 后，剩余的其它元素中的最小值是多少？

输入
第一行两个整数 N 和 Q，分别表示 序列的长度和询问次数
第二行N个整数 Ai，表示序列
第三行Q个整数 ki，表示Q次询问，第 i 次询问是去掉 Aki

输出
共Q行，第 i 行表示第 i 次询问结果

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,maxs=0x3f3f3f3f;
int n,q;
int a[N],k,dp[N];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int x,y;
    x=y=0;//x最小值下标，y次小值下标
    a[0]=maxs;
    for(int i=1;i<=n;i++){
        if(a[x]>a[i]){
            y=x;
            x=i;
        }
        else if(a[y]>a[i]) y=i;
    }
    for(int i=1;i<=q;i++){
        scanf("%d",&k);
        if(k==x) printf("%d\n",a[y]);
        else printf("%d\n",a[x]);
    }//x,y只是下标！！要输出最小值
    return 0;
}
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