备案用个人单页网站,定制网站与模板网站,wordpress前端页面模板,网站导航栏按钮近期题目来自校赛#xff0c;赛前训练#xff0c;省赛热身#xff0c;河北ccpc正式比赛。
题目一#xff1a;
题目描述#xff1a;
由于第m个台阶上有好吃的薯条#xff0c;所以薯片现在要爬一段m阶的楼梯. 薯片每步最多能爬k个阶梯#xff0c;但是每到了第i个台阶赛前训练省赛热身河北ccpc正式比赛。
题目一
题目描述
由于第m个台阶上有好吃的薯条所以薯片现在要爬一段m阶的楼梯. 薯片每步最多能爬k个阶梯但是每到了第i个台阶薯片身上的糖果都会掉落ai个现在问你薯片至少得掉多少糖果才能得到薯条
输入
多组数据输入每组数据第一行输入两个数字m(1m1000),k(1km),接下来有m行每一行输入ai(0ai1000)表示第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-2n-3......n-k。
也就是说
f(n)anmin(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行每行给出一个宝藏的位置xiyizi 以及价值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
样例输出
66 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年出生n3年死去。
出生一年以后可以生育也就是n1年开始生育一年可以生一只宝宝。
定义第n年动物总数为an给定n返回an/a(n-1)最多保存小数点后十位
第一年有一只
思路一定义f(n)为第n年新出生的动物个数则f(n)f(n-1)f(n-2),前两项为1而每年的总数也就是三项求和而已。
每年出生的数量为1123581321
每年总数就是12410162642
发现是斐波那契数列
思路二直接从总数入手定义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)越来越接近黄金分割
手写了求解过程。可能写的不规范但是就是表达这个意思。 只要数列满足X(n) X(n-1) X(n-2)无论前两个值是多少都满足黄金分割的条件而斐波那契数列是最简单的特例前两个元素均为1
数学家还发现了费马大定理和这个数列的关系(费马大定理的证明三百五十年)并应用到诸多领域比如加密。有兴趣自行了解。 题目四
省赛没有原题。十六支队伍过了这个题。
https://blog.csdn.net/hebtu666/article/details/79964233
参考我前面的文章dp入门篇那个会了这个就会。
参考萌新题
现场因为对c不熟没敢压空间规规矩矩的写了一遍还因为多打了一行罚了时跟智障一样。。。 题目五
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};
queueint q[1005];
int main()
{int ak; cinak;while(ak--){for(int i1;in;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 i1;in;i) cina[i];for(int i1;im;i) cinb[i];for(int i1;in;i){q[a[i]].push(i);if(q[a[i]].size()k){pa[i]q[a[i]].front();q[a[i]].pop();}}for(int i1;in;i)while(!q[i].empty()) q[i].pop();for(int i1;im;i){q[b[i]].push(i);if(q[b[i]].size()k){pb[i]q[b[i]].front();q[b[i]].pop();}}for(int i1;in;i){for(int j1;jm;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。。就连套路都不会用了。
平时递归关系自己推自己推自己推。
