ccpc河北大学生程序设计竞赛dp小总结

迷南。 2022-05-24 06:09 307阅读 0赞

近期题目来自校赛，赛前训练，省赛热身，河北ccpc正式比赛。

# 题目一： #

题目描述：

由于第m个台阶上有好吃的薯条，所以薯片现在要爬一段m阶的楼梯.  
薯片每步最多能爬k个阶梯，但是每到了第i个台阶，薯片身上的糖果都会掉落ai个，现在问你薯片至少得掉多少糖果才能得到薯条？

输入：

多组数据输入，每组数据第一行输入两个数字m(1<m<=1000),k(1<=k<m),接下来有m行，每一行输入ai(0<ai<=1000)，表示第i个台阶会掉落的糖果.

输出：

对于每组数据，输出至少要牺牲的糖果数.

样例输入

5 2  
1 2 3 4 5  
6 2  
6 5 4 3 2 1

样例输出

9  
9

分析：经过的数字全部加起来，为一个累加和，求最小累加和

递推关系：

定义f(n)为必须到第n个台阶的最少累加和

分析可以如何得到f(n)，我们通过跳一步，可以怎么跳到第n个台阶呢？

可以从第n-1个台阶跳到这里，可以n-2，n-3......n-k。

也就是说，

f(n)=an+min(f(n-1),f(n-2),......f(n-k))

必须到第n个台阶的最少累加和，就等于能跳到这里的所有位置中，最小的那个f()，跳过来（也就是加上本身）。

注意：前k个台阶可以从起点直接跳过来，贪心思想，经过任何多余的数字都不会是最优解。所以前k个f(n)直接赋值an.

也可以维持单调队列把时间降到线性，不过o(n\*k)已经足够过了。

# 题目二： #

题目描述：

JiangYu的小金库是一个三维立体的空间，大小为XYZ，里面每个位置都藏着各种价值的宝物，既然是宝物价值自然非同一般，可正可负。

可恶的花花得知了这一切，想要偷走其中的珍宝们。

可是Jiangyu的小金库安保措施十分严密，花花只有一次行动的机会，他决定偷走一个价值尽可能大的长方体区间。

那么他最大能偷走多少钱的宝物呢？

输入：

第一行给出三个正整数 X,Y,Z

第二行一个整数n， 宝藏的数量

接下来n行，每行给出一个宝藏的位置xi，yi，zi， 以及价值ci

保证宝藏位置不重复。 （1 \\leq X,Y,Z \\leq 201≤X,Y,Z≤20)

（1 \\leq n \\leq X \\times Y \\times Z1≤n≤X×Y×Z)

（1 \\leq xi \\leq X1≤xi≤X)

（1 \\leq yi \\leq Y1≤yi≤Y)

（1 \\leq zi \\leq Z1≤zi≤Z)

（-1e9 \\leq ci \\leq 1e9−1e9≤ci≤1e9)

输出：

一个整数，最大的价值

样例输入

2 2 2  
8  
1 1 1 10  
1 1 2 9  
1 2 1 10  
1 2 2 9  
2 1 1 10  
2 1 2 9  
2 2 1 -1  
2 2 2 10

样例输出

[https://blog.csdn.net/hebtu666/article/details/82788866][https_blog.csdn.net_hebtu666_article_details_82788866]这个网址写了详细讲解哦。。。最好要看看

首先要明白一维最大子数组问题，设dp\[n\]的含义为必须以an结尾的数组中的最大和。

所以dp\[n\]就是，每一个以在n前面的结尾的最大值，加上an.

二维方法：转化为一维来做。**枚举长度为原矩阵长度的所有矩阵**。然后压成一维来做。

**时间：**

因为有n个开头，每个开头有n-1,n-2......1个结尾，所以枚举的时间复杂度为o(n^2)。

为了节省时间，利用预处理数组思想，定义长宽和原矩阵一样的矩阵gg。

每列满足第n列k行的值为sum(l\[0\]\[n\]+l\[1\]\[n\]....l\[k\]\[n\]),可以o(n\*m)做到(nm为长宽).然后枚举到某矩阵的时候直接根据gg得出。整体做到o(n^2)枚举并求和。然后按一维做。整体o(n^3)

三维：并没有什么高大上的优化，也是枚举每一个长宽固定的长方体，压缩至二维，然后按二维做。

# 题目三： #

热身赛，并没有原题，手打。

过的队伍不多

一种动物，出生到死亡只有三年，即n年出生，n+3年死去。

出生一年以后可以生育，也就是n+1年开始生育，一年可以生一只宝宝。

定义第n年动物总数为an，给定n，返回an/a(n-1)，最多保存小数点后十位

第一年有一只

思路一：定义f(n)为第n年新出生的动物个数，则f(n)=f(n-1)+f(n-2),前两项为1，而每年的总数也就是三项求和而已。

每年出生的数量为1，1，2，3，5，8，13，21

每年总数就是1，2，4，10，16，26，42

发现是斐波那契数列

思路二：直接从总数入手，定义f(n)为第n年的总数

如何求出an/a(n-1):要看有多少动物能活到n年，活不到n年的也不能在第n年生育，活到n年的动物每人生一个，所以an就是二倍的能活到n年的动物。求此数方法很多，在此只说一个：

f(n-1)-(1/2)f(n-3)

去年的数量减去，去年还活着的今年就死了的数量。

这个数乘二，得出答案f(n)=2f(n-1)-f(n-3),其实本质还是斐波那契，因为f(n-1)=f(n-2)+f(n-3)，带入以后发现f(n)=f(n-1)+f(n-2)。

式子写出来了，但是原题数据范围是10^1000，不能一项一项推过去。

尝试发现，几十项之后，an/a(n-1)的十位小数之内都没有变过，所以当数字较大时直接输出第五十项即可。

本题结束

但是还有点别的东西想写

# 斐波那契的美 #

万物之美，总能找到斐波那契数列的规律。随着n的增加，an/a(n-1)越来越接近黄金分割

手写了求解过程。可能写的不规范，但是就是表达这个意思。

![20180522110138159][]

只要数列满足X(n) = X(n-1) + X(n-2)，无论前两个值是多少，都满足黄金分割的条件，而斐波那契数列是最简单的特例：前两个元素均为1

数学家还发现了费马大定理和这个数列的关系(费马大定理的证明，三百五十年)，并应用到诸多领域（比如加密）。有兴趣自行了解。

# 题目四： #

省赛，没有原题。十六支队伍过了这个题。

[https://blog.csdn.net/hebtu666/article/details/79964233][https_blog.csdn.net_hebtu666_article_details_79964233]

参考我前面的文章，dp入门篇，那个会了这个就会。

参考萌新题![20180522110445853][]

现场因为对c++不熟，没敢压空间，规规矩矩的写了一遍，还因为多打了一行罚了时，跟智障一样。。。

# 题目五 #

[http://newoj.acmclub.cn/contests/1359/problem/6][http_newoj.acmclub.cn_contests_1359_problem_6]

题意：最长公共子序列，要求序列每个元素重复k次，比如1122重复两次，111222重复三次。

输入两个字符串和k，输出长度。

最长公共子序列的一个变形。。。

动态规划。设dp\[i\]\[j\]表示a串处理到i位置，b串处理到j位置的答案。预处理出从a串i位置向前数，第k个与i位置数  
字相同的位置p\[i\]，用相同方式处理出B串的q\[i\]。  
则转移方程为dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i\]\[j-1\],dp\[i-p\[i\]\]\[j-q\[j\]\]+1),其中第三种转移必须在a\[i\]=b\[j\]的情况下转移。

#include <bits/stdc++.h>
    using namespace std;
    int k,n,m,dp[1005][1005];
    int a[1005],b[1005];
    int pa[1005]={0},pb[1005]={0};
    queue<int> q[1005];
    int main()
    {
        int ak; cin>>ak;
        while(ak--)
        {
            for(int i=1;i<=n;i++)
                while(!q[i].empty()) q[i].pop();
            scanf("%d%d%d",&k,&n,&m);
            memset(dp,0,sizeof(dp));
            memset(pa,0,sizeof(pa));
            memset(pb,0,sizeof(pb));
            for(int i=1;i<=n;i++) cin>>a[i];
            for(int i=1;i<=m;i++) cin>>b[i];
            for(int i=1;i<=n;i++)
            {
                q[a[i]].push(i);
                if(q[a[i]].size()==k)
                {
                    pa[i]=q[a[i]].front();
                    q[a[i]].pop();
                }
            }
            for(int i=1;i<=n;i++)
                while(!q[i].empty()) q[i].pop();
                
            for(int i=1;i<=m;i++)
            {
                q[b[i]].push(i);
                if(q[b[i]].size()==k)
                {
                    pb[i]=q[b[i]].front();
                    q[b[i]].pop();
                }
            }
            
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    if(a[i]==b[j] && pa[i]!=0 && pb[j]!=0)
                        dp[i][j]=dp[pa[i]-1][pb[j]-1]+k;
                }
            }
            printf("%d\n",dp[n][m]);
        }
        return 0;
    }

代码都是比赛时候写的，真的不想找来贴了。

### 最后总结经验教训： ###

###  ###

注意细节，注意细节，注意细节

多种思路，多种思路，多种思路

递归关系自己推，比如背包，你要是看套路。。。Emmm。。就连套路都不会用了。

平时递归关系自己推，自己推，自己推。

[https_blog.csdn.net_hebtu666_article_details_82788866]: https://blog.csdn.net/hebtu666/article/details/82788866
[20180522110138159]: /images/20220524/520f520f1b7e428490da6e1f152db128.png
[https_blog.csdn.net_hebtu666_article_details_79964233]: https://blog.csdn.net/hebtu666/article/details/79964233
[20180522110445853]: /images/20220524/480846d9009f4a119cd6bfd1964329e7.png
[http_newoj.acmclub.cn_contests_1359_problem_6]: http://newoj.acmclub.cn/contests/1359/problem/6