外贸网站搜索引擎优化方法,东莞关键词优化推广,重庆app定制,酒店专业培训网站建设1.双11的红包雨
问题描述
双11到了#xff0c;据说这2天会下红包雨#xff0c;每个红包有不同的价值#xff0c;小k好开心#xff0c;但有个规则#xff0c;就只能接掉落在他身旁的10米范围内的红包#xff08;0-10这11个位置#xff09;。小k想尽可能的多抢红包…1.双11的红包雨
问题描述
双11到了据说这2天会下红包雨每个红包有不同的价值小k好开心但有个规则就只能接掉落在他身旁的10米范围内的红包0-10这11个位置。小k想尽可能的多抢红包这样就可以去买一个华为手机小k每秒种只能在移动不超过一米的范围内接住红包。小k一开始站在5这个位置因此在第一秒他只能接到4,5,6这三个位置中其中一个位置上的红包。问小k最多可能接到多少价值的红包
输入
第一行输入整数n表示共有多少个红包n1000
后面n行表示n个红包每行有三个整数分别表示红包掉落的位置、时间和价值。
输出
小k接到的红包价值之和。
输入样例
8 3 18 5 7 13 7 1 8 10 2 7 13 10 20 1 3 17 8 10 2 123 3 13 45
输出样例
81
每个时刻的状态只有三种 继续站在原地 向左移动 向右移动 此外还要注意一点在0处不能向左移动在11处不能向右移动。 状态转移方程 dp[i][j]maxn(dp[i1][j−1]dp[i1][j]dp[i1][j1])dp[i][j]dp[i][j]maxn(dp[i1][j-1]dp[i1][j]dp[i1][j1])dp[i][j] dp[i][j]maxn(dp[i1][j−1]dp[i1][j]dp[i1][j1])dp[i][j]
#includebits/stdc.h
using namespace std;int dp[1010][12]; // dp[i][j]表示i时刻j位置开始出发到最终时间点所获得的最大红包数
//两个数中的最大值
int max_2(int a, int b)
{return (ab) ? a :b;
}
//三个数中的最大值
int maxn(int a, int b, int c)
{int max (ab) ? a : b;return (maxc) ? max : c;
}
// 计算最优值
// 状态转移方程为dp[i][j]maxn(dp[i1][j-1]dp[i1][j]dp[i1][j1])
void maxValue(int max_time)
{//对于每个时间所有位置从结束计算到开头//当记录了上一时刻的最大值可以以此为参照计算出所有位置该时刻的最大值//两重循环之后可以获取所有位置所有时刻的最大值for(int imax_time-1; i0; i--){for(int j0; j12; j){if(j 0) // 在第0位置下一秒只能原地或向右移动 dp[i][j] max_2(dp[i1][j],dp[i1][j1]) dp[i][j];else if(j 11) // 在第11位置下一秒只能原地或向左移动 dp[i][j] max_2(dp[i1][j],dp[i1][j-1]) dp[i][j];else// 其他情况每个时刻能够向左右或者不动dp[i][j] maxn(dp[i1][j-1],dp[i1][j],dp[i1][j1]) dp[i][j];}}
}
int main()
{int n;cin n;int location, time, value;int max_time -1;memset(dp, 0, sizeof(dp));// 保存输入的数据到数组中 while(n--){cin location time value;dp[time][location] value;if(time max_time) max_time time;}// 求出最大的红包maxValue(max_time);// dp[1][4]为初始时刻、初始位置对应的价值已经从最后时刻推回来了所以一定是最优解。cout dp[1][4] endl;return 0;
}2.最大连续字段和
问题描述略
只有两种情况
某位置最大连续子段为它本身最大连续子段长度至少为 2至少包含它之前的一个节点
取两者的最大值递推方程 dp[i]max(dp[i−1]arr[i],arr[j])dp[i]max(dp[i-1]arr[i],arr[j]) dp[i]max(dp[i−1]arr[i],arr[j])
#includebits/stdc.h
using namespace std;
int main()
{int num;cinnum;int arr[num],dp[num]; // 读数据for(int i0;inum;i){ cinarr[i];dp[i]0;}// 初始化dp[0]max(arr[0],0);for(int i1;inum;i){// 状态转移方程dp[i]max(arr[i],dp[i-1]arr[i]); }sort(dp,dpnum);//排序coutdp[num-1];//输出最大值 return 0;
}3.减肥的小k 2
题目描述
小K是个苦命的孩子他的师傅为了多赚钱以减肥为理由让他去采药并说不完成不能吃饭。野地里有许多不同的草药采每一株都需要一些时间每一株也有它自身的价值。要求在规定的时间t里采到的草药的总价值最大。
输入
第一行有2个整数T(1≤T≤1000)和M(1≤M≤100)一个空格隔开T代表总共能够用来采药的时间M代表山洞里的草药的数目。
输出
1个整数表示在规定的时间内可以采到的草药的最大总价值。
输入样例
70 3 71 100 69 1 1 2
输出样例
3
#includebits/stdc.h
using namespace std;
const int MAXN 1005; // 最大草药数量
const int MAXT 1005; // 最大采药时间
int t[MAXN], v[MAXN]; // t[i]是第i个草药的采摘时间v[i]是第i个草药的价值
int dp[MAXT]; // dp[j]表示用j的时间采摘草药的最大价值
int main()
{int T, M;cin T M; // T是总时间M是草药数量for (int i 1; i M; i){cin t[i] v[i]; // 输入每个草药的采摘时间和价值}memset(dp, 0, sizeof(dp)); // 初始化dp数组为0for (int i 1; i M; i){for (int j T; j t[i]; j--){// 从后往前遍历防止重复计算dp[j] max(dp[j], dp[j-t[i]]v[i]); // 状态转移方程}}cout dp[T] endl; // 输出用T的时间采摘草药的最大价值return 0;
}4.最长非连续公共子序列
题目描述
略
dp [ i ] [ j ] 表示第一个串前 i 个与第二个串前 j 个组成的 lcs 子问题
状态转移方程
如果当前指针两个字符相同 dp[i][j]dp[i−1][j−1]1dp[i][j] dp[i-1][j-1] 1 dp[i][j]dp[i−1][j−1]1 如果当前指针两个字符不同
需要从前面的两个状态恢复两个状态分别为 dp [ i-1 ] [ j ] 和 dp [ i ] [ j-1 ] 将它们的最大值作为该位置的状态 dp[i][j]max(dp[i−1][j],dp[i][j−1])dp[i][j] max(dp[i-1][j], dp[i][j-1]) dp[i][j]max(dp[i−1][j],dp[i][j−1])
#includebits/stdc.h
using namespace std;
int lcs(string s1, string s2)
{// 初始化int m s1.size();int n s2.size();int dp[m1][n1];memset(dp, 0, sizeof(dp));// 对于ab两个字符串分别设定两个指针ab// 指针分别从头开始向后移动取两个字符串前ij个// 这样就存在两种情况// 1.两个指针处的字符相同说明存在子串dp[i][j] dp[i-1][j-1] 1 从ab指针同时退后两个的情况1// 2.如果两个指针指向的字符不相同说明不能从 i-1j-1 跳转到 ij但是为了保存之前的结果需要存储当前// 的最优解当前是将两个指针同时前进1个单位最优解一定在左指针前进一个或右指针前进一个里面选// 这就推出了最终的状态转移方程for (int i 1; i m; i) {for (int j 1; j n; j) {if (s1[i-1] s2[j-1]) {dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] max(dp[i-1][j], dp[i][j-1]);}}}return dp[m][n];
}
int main()
{string s1 ABCD;string s2 ABDE;cout lcs(s1, s2) endl; // 输出 2即 AB 是最长非连续公共子序列return 0;
}5.切钢条
题目描述
一家公司购买长钢条将其切割成短钢条出售切割本身没有成本长度为i的短钢条的价格为Pi。那给 定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。 输入要求
输入钢条的长度n。
输出要求
输出获得的最大收益。
dp [ i ] 表示长度为 i 的情况下的最大利润
共有 10 种切法所以要设置两重循环目的是获得每个长度下的最优解有了小长度才能以此为基础获取大长度的最优解
有两种状态切或不切切掉之后要考虑价值是否增加所以产生了状态转移方程 dp[i]max(pi[j]dp[i−j],dp[i])dp[i] max(pi[j] dp[i - j], dp[i]) dp[i]max(pi[j]dp[i−j],dp[i])
#includebits/stdc.h
using namespace std;
int pi[11] { 0,1,5,8,9,10,17,17,20,24,30 }; //记录已知长度钢条价值
int dp[1000] { 0 };//记录动态规划结果
int findMaxVal(int n)
{if (n 0) // 若n为0直接返回return 0;for (int i 1;i n;i) {for (int j 1;j i j 10;j) { // 第一刀最多切10种dp[i] max(pi[j] dp[i - j], dp[i]);//遍历所有切法}}return dp[n];
}
int main()
{int n;cin n;memset(dp,0,sizeof(dp));// 判断一下是否超过10记录除数和余数int chushu 0;int yushu 0;int res_10 0;int res 0;if(n10){chushu n / 10;yushu n % 10;res_10 findMaxVal(10);res_10 * chushu;res res_10 findMaxVal(yushu);}else{res findMaxVal(n); }cout res endl;return 0;
}6.合格的盗贼
题目描述
一条街上有N个商铺商铺i有价值V[i]的物品你有足够的时间在晚上光顾所有的商店人们称呼你为盗贼每个商店都有一个报警器会在晚上报警但是只有相邻的2个商店同时报警时警察才会出动你需要证明你是个合格的盗贼。
输入要求
第一行一个整数N100商店数。 第二行N个整数每个商店的价值
输出要求
输出偷盗的最大价值。
假设在考虑第i个只有两种个情况只有这两种情况收益最大按照这种思想往下推很简单就能求出最大利润
第一种ii - 2第二种i - 1
#includebits/stdc.h
using namespace std;
int dp[101] { 0 };
int findMaxValue(int n)
{if (n 1)return dp[0];else if (n 2)return max(dp[0], dp[1]);dp[1] max(dp[0], dp[1]);for (int i 3;i n;i){// 只有两种选择假设有 a b c 三个连续的位置// 只有两种选择不会触发警报// 1. a c// 2. b// 依据这个限制条件可以给出状态转移方程dp[i - 1] max(dp[i - 2], dp[i - 3] dp[i - 1]);}return dp[n - 1];
}
int main()
{int n;cin n;for (int i 0;i n;i) {cin dp[i];}int res findMaxValue(n);cout res endl;return 0;
}
