提供秦皇岛网站建设价格,洛阳网站建设优惠公司,wordpress自定义钩子,百度广告费动态规划 确定递推状态#xff1a; f(n)解释 确定递推公式 程序实现
优化#xff1a; 去除冗余状态 状态重定义 优化转移过程 斜率优化
优化-递归记忆化 if arr[n] return arr[n]递归记忆化(正向求解-递归) 或 改变求解顺序#xff08;逆向递归求解-循环#xff09; f(n)解释 确定递推公式 程序实现
优化 去除冗余状态 状态重定义 优化转移过程 斜率优化
优化-递归记忆化 if arr[n] return arr[n]递归记忆化(正向求解-递归) 或 改变求解顺序逆向递归求解-循环 解决效率问题 用long long 或者更大的解决数值溢出不够大问题 HZOJ 38 兔子繁殖问题 确定递推状态 f(n)为第n个月的时候兔子的数量确定递推公式: f(1)1 | f(2)2 | f(n)f(n-1)f(n-2)程序实现 #include iostream
using namespace std;
#define MAX_N 100
int digui_jiyihua_arr[MAX_N5]{0};int f(int n){if(n2) return n;if(digui_jiyihua_arr[n])return digui_jiyihua_arr[n]; //优化-增加记忆点,解决超时问题digui_jiyihua_arr[n]f(n-1)f(n-2);return digui_jiyihua_arr[n];
}
void acm_1_14_digui_jiyihua_test(){int n;cinn;cout f(n) endl;
}改变求解顺序 从低到高 long long acm_1_14_digui_jiyihua_f[105]{0};
void acm_1_14_digui_jiyihua_test2(){int n;cinn;acm_1_14_digui_jiyihua_f[1]1;acm_1_14_digui_jiyihua_f[2]2;for(int i3;in;i){acm_1_14_digui_jiyihua_f[i]acm_1_14_digui_jiyihua_f[i-1]acm_1_14_digui_jiyihua_f[i-2];}cout acm_1_14_digui_jiyihua_f[n] endl;
}//
// Created by cry on 2024/3/24.
//
#include vector
#include iostream
using namespace std;
#define MAX_N 100
long long digui_jiyihua_arr[MAX_N5]{0};long long f(int n){if(n2) return n;if(digui_jiyihua_arr[n])return digui_jiyihua_arr[n]; //优化-增加记忆点,解决超时问题digui_jiyihua_arr[n]f(n-1)f(n-2);return digui_jiyihua_arr[n];
}
void acm_1_14_digui_jiyihua_test(){int n;cinn;cout f(n) endl;
}
//大整数
class BigInt:
public vectorint{public:BigInt(){push_back(0);}BigInt(int x){this-push_back(x);process_digit();//处理大整数进位问题}//重载运算BigInt operator(const BigInt a){for(int i0;ia.size();i){if(i size()) //如果位数超出了{push_back(a[i]);}else at(i)a[i];}process_digit();return *this;}//重载加法运算BigInt operator(const BigInt a){BigInt ret(*this);//拷贝一下当前reta;return ret;}//重载左移运算符//进位void process_digit() {for (int i 0; i size(); i) {if (at(i) 10) continue; //当前位置的值小于10不需要处理//当前位置的值大于10就进位if (i size() - 1) push_back(0); //增加一位at(i 1) at(i) / 10;at(i) % 10;}return ;}
};
// 重写左移运算符
ostream operator(ostream out,const BigInt a){for(int ia.size()-1;i0;i--){out a[i];}return out;
}
BigInt acm_1_14_digui_jiyihua_f[105]{0};
void acm_1_14_digui_jiyihua_test2(){int n;cinn;acm_1_14_digui_jiyihua_f[1]1;acm_1_14_digui_jiyihua_f[2]2;for(int i3;in;i){acm_1_14_digui_jiyihua_f[i]acm_1_14_digui_jiyihua_f[i-1]acm_1_14_digui_jiyihua_f[i-2];}cout acm_1_14_digui_jiyihua_f[n] endl;
}
int main() {acm_1_14_digui_jiyihua_test2();return 0;
}python解法 只需要记忆化就行了类型不会出问题 #第一代缺点效率低 且 数据类型不够大
# dp_1(65) 直接跑不完
def dp_1(n):if(n2):return nreturn dp_1(n-1)dp_1(n-2)
# 解决添加记忆化
MAX_N100
arr[0]*(MAX_N5)
def dp_2(n):if(n2):return nif arr[n]:return arr[n]arr[n]dp_2(n-1)dp_2(n-2)return arr[n]
nint(input())
print(dp_2(n))
# 改变求解顺序
def dp_3(n):arr[0]*(MAX_N5)if(n2):return narr[1]1arr[2]2for i in range(3,n1):arr[i]arr[i-1]arr[i-2]return arr[n]
print(dp_3(n))容斥原理的基本思想
在计数的时候为了没有重复 没有遗漏再不考虑重叠的情况把包含于某内容的所有对象数目先计算出来然后把计数时重复的计算的数目排斥出去
加多的减掉减多了加回来
结果既无遗漏又无重复—容斥原理 钱币问题 确定递推状态 f[i][j]表示用i种钱币凑足j元钱的方法总数 1 2 5 f(2)(5) ,前两种钱币凑5块有1 2 2 1 1 1 2 1 1 1 1 1三种 确定递推公式 拆分分成两个不相交的子集 a. 没有使用第i种钱币 b. 使用了第i种钱币 f[i][j]f[i-1][j]f[i][j-w[i]] w:1 2 5 f(3)(5)f(3-1)(5)f(3)(5-5) f(2)(5)f(3)(0) f(1)(5)f(2)(3)f(3)(0) f(1)(5)f(1)(3)f(2)(1)f(3)(0) f(1)(5)f(1)(3)f(1)(1)f(2)(0)f(3)(0) f(0)(5)f(0)(3)f(0)(1)f(1)(0)f(2)(0)f(3)(0) 0000111 3 程序实现 //
// Created by cry on 2024/3/27.
//
#include iostreamusing namespace std;
#define MAX_N 10000
#define MAX_M 20
int w[MAX_N5];
int f[MAX_M5][MAX_N5]; //前m种钱币拼凑n元钱
void acm_1_14_dp_money_test(){int m,n;cin m n;for(int i1;im;i) { //钱币类型遍历cin w[i];}for(int i1;im;i){f[i][0]1; //前i种钱币凑0元钱为1种// 因为f(2)(5)f(3)(0)f(3)(5)// 314所以f(3)(0)为1for (int j 1; j n; j) {f[i][j]f[i-1][j];if(jw[i])continue; //小于第i种钱币的面额f[i][j]f[i][j-w[i]];f[i][j] % 9973;}}cout f[m][n] endl;
}使用python实现 def get_dp_dp_money(m,n,w):# f[[0]*(n5)]*(m5) //同一个地址f[[0]*(n5) for _ in range(m5)] # 不同地址for i in range(1,m1):f[i][0]1 # 终止条件for j in range(1,n1):f[i][j]f[i-1][j]if(jw[i-1]):continue #f(1)(3)没有值为0f[i][j]f[i][j-w[i-1]]f[i][j]%9973print(f[m][n])if __name____main__:m,nlist(map(int,input().split( )))wlist(map(int,input().split( )))w.append(0)get_dp_dp_money(m,n,w)HZOJ40爬楼梯 确定递推状态 f[n]表示n级的方法总数 1 2 5 f(2)(5) ,前两种钱币凑5块有1 2 2 1 1 1 2 1 1 1 1 1三种 确定递推公式 拆分分成两个不相交的子集且相加为全集 a. 最后一步跨两步走到f[n-2]台阶的方法总数 b. 最后一步跨三步走到f[n-3]台阶的方法总数 f[n]f[n-2]f[n-3] 程序实现 #include iostream
using namespace std;
#define MAX_N 500
int res[MAX_N5];
void acm_1_14_dp_palouti_test(){int n;res[0]1;res[1]0;res[2]1;cin n;for(int i3;in;i){res[i]res[i-2]res[i-3];}cout res[n]endl;
}python def palouti():nint(input())res[0]*505res[1]0res[0]1res[2]1;for i in range(3,n1):res[i]res[i-2]res[i-3]print(res[n])palouti()HZOJ 41墙壁涂色 n块墙壁可以涂k种颜色 墙壁呈现环形相邻两块墙壁不能相同 确定递推状态 f[n][i][j]n块墙壁首墙壁i种颜色尾墙壁j种颜色的方案数 确定递推公式 拆分分成两个不相交的子集且相加为全集 a. 最后一步跨两步走到f[n-2]台阶的方法总数 b. 最后一步跨三步走到f[n-3]台阶的方法总数 f[n][i][j]f[n-1][i][k] 且k!j 最后累加: 首尾可能相同 f[n][i][j] 且 i!j的项累加 :剔除首尾相同的 边界条件f[1]{1,0,0, 0,1,0 0,0,1} 程序实现 解决内存超界的方法使用滚动数组 //
// Created by cry on 2024/3/27.
//
#include iostream
using namespace std;
#define MAX_N 1000
#define MAX_K 10
int ys[2][MAX_K5][MAX_K5]; //使用滚动数组解决内存超限问题
void acm_1_14_dp_qiangBiTuSe_test(){int n,k;cin nk; //读取数据n块墙壁涂k种颜色for(int i1;ik;i){ys[1][i][i]1;} //初始化f[1] ,对角线元素为1其余为0for(int ws2;wsn;ws){for(int i1;ik;i){for(int j1;jk;j){ys[ws %2][i][j]0;for(int l1;lk;l){if(lj){ continue;}ys[ws%2][i][j]ys[(ws-1)%2][i][l];}}}}//提出ij的部分int ans0;for(int i1;ik;i){for(int j1;jk;j){if(ij){ continue;}ansys[n%2][i][j];}}cout ans endl;}python #!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 Cry, Inc. All Rights Reserved
#
# Time : 2024/3/27 15:03
# Author : Cry
# File : 墙壁涂颜色.py
# IDE : PyCharmMAX_N 1000
MAX_K 10
# f [[[0] * (MAX_K 5)] * (MAX_K 5)] * 2 # f 是一个包含两个元素的列表。每个元素都是一个包含 (MAX_K 5) * (MAX_K 5) 个元素的二维列表。这意味着 f[0] 和 f[1] 是两个指向内存中相同位置的引用因此如果你修改 f[0]f[1] 也会受到影响
f [[[0] * (MAX_K 5) for _ in range(MAX_K 5)] for _ in range(2)]
#f 是一个包含两个元素的列表。每个元素都是一个包含 (MAX_K 5) * (MAX_K 5) 个元素的二维列表。但是与第一行代码不同的是这里的两个二维列表是独立的它们并不共享内存中的相同位置。因此如果你修改 f[0]f[1] 不会受到影响。def qiangbitumo():n, k list(map(int, input().split( )))for i in range(1, k 1):f[1][i][i] 1 # 对角线元素为1for ws in range(2, n 1):for i in range(1, k 1):for j in range(1, k 1):f[ws % 2][i][j] 0for l in range(1, k 1):if l j:continuef[ws % 2][i][j] f[(ws - 1) % 2][i][l];ans 0for i in range(1, k 1):for j in range(1, k 1):if i j:continueans f[n % 2][i][j]print(ans)qiangbitumo() 洛谷P1025 数的划分 确定递推状态 f(i)(j)数字i分成j份的方法总数 确定递推公式 拆分分成两个不相交的子集且相加为全集 a. 拆分的方案中有1的方案总数 去掉1剩下的总和为f(i-1)(j-1) b. 拆分的方案中没有1的方案总数每份都减去1减j个1f(i-j)(j) 递推公式f[i][j]f[i-1][j-1]f[i-j][j] 边界条件f[0][0]1 f[i][1]1 程序实现 学习在固定份数的前提统计全集分成两个集合 按照有1和没有1有1减1没有1每份都减去1 //
#include iostream
using namespace std;
#define MAX_N 200
#define MAX_K 6
int f1[MAX_N5][MAX_K5];
void acm_1_14_dp_shudehuafen_test(){int n,k;cin n k;
// f(i)(j)f(i-1)(j-1)f(i-j)(j)f1[0][0]1; //将0拆成0份方法为1for(int i1;in;i){
// 设置边界条件f1[i][1]1; //将i拆成1份拆成方法总数为1
// f[0][j] 0 f[i][1]1for(int j1,Jmin(i,k);jJ;j){f1[i][j]f1[i-1][j-1]f1[i-j][j];}}cout f1[n][k] endl;
}
int main(){acm_1_14_dp_shudehuafen_test();return 0;
}python # 定义最大值
MAX_N 200
MAX_K 6# 初始化动态规划数组
f1 [[0] * (MAX_K 5) for _ in range(MAX_N 5)]def acm_1_14_dp_shudehuafen_test():# 输入 n 和 kn, k map(int, input().split())# 初始化边界条件f1[0][0] 1# 动态规划过程for i in range(1, n 1): #求1到n的每个数的分成k份的份数f1[i][1] 1 #分1份为1for j in range(1, min(i, k) 1):f1[i][j] f1[i - 1][j - 1] f1[i - j][j]# 输出结果print(f1[n][k])acm_1_14_dp_shudehuafen_test()洛谷1028 数的计算 确定递推状态 f(i)以i开头的合法数列数量 确定递推公式 拆分分成两个不相交的子集且相加为全集 a. 不扩展只有一个i 1个 b. 能扩展的从i/2 i/2-1 i/2-2 … 1 递推公式f[i]1Σf[j] (ji/2) 边界条件f[1]1 f[i][1]1 程序实现 学习在固定份数的前提统计全集分成两个集合 按照有1和没有1有1减1没有1每份都减去1 #include iostream
using namespace std;
#define MAX_N 1000
int f2[MAX_N5]{0};
void acm_1_14_dp_shudejisuan_test(){int n;cin n;//边界条件f2[0]0;for(int i1;in;i){f2[i]1;for(int j1;ji/2;j){f2[i]f2[j]; //f[i]1Σ f[i/2]}}cout f2[n] endl;
}
int main(){acm_1_14_dp_shudejisuan_test();return 0;
}python def getNum():nint(input())f[0]*1005for i in range(1,n1):f[i]1for j in range(1,i//21):f[i]f[j]print(f[i])
getNum()洛谷P1038 神经网络 使用拓扑序列计算神经元 CiΣ(WijCj) - Ui 拓扑序用于AOV网中拓扑序是先行关系的 序列前面的神经元是后面神经元的先行活动。 拓扑序生成原理 将入度为0的点输出(无前驱的活动)将 上一步输出的节点所在的弧都删除重复第一第二步若输出顶点数 有向涂顶点数则有回路否则输出的即为拓扑序列 //
// Created by cry on 2024/3/28.
//
#include iostream
#include vector
#include queueusing namespace std;
#define MAX_N 100
//CiΣ(w3ijCj) - Ui
int c[MAX_N5];//状态值 Ci
int u[MAX_N5];//被减去的 Ui
int w3[MAX_N5][MAX_N5 ]; //wij
vectorint g[MAX_N5];//每个节点指向的节点
int outdeg[MAX_N5];//出度
int indeg[MAX_N5];//出度
void acm_1_14_dp_shenjingwangluo_test(){//读取数据int n,p;cin n p;//读取每个节点的c值和u值for( int i1;in;i){cin c[i] u[i];//如果是输入层节点直接为-u[i]if (c[i]0)c[i]-u[i];}//读取若干条边的值for(int i0,a,b,W3;ip;i){cin a b W3;w3[a][b]W3; //w3[i][j]indeg[b]1;//入度1outdeg[a]1; //出度1g[a].push_back(b); //添加出边}queueint q;//将入度为0的点都加入到队列将输入层节点都加进去(入度为0)for(int i1;in;i){if(indeg[i])continue;q.push(i);}//开始按照拓扑序依次计算每个序列的值while(!q.empty()){int indq.front(); //计算当前节点状态值q.pop();if(c[ind]0){ //当前节点被激活for(int i0;ig[ind].size();i){int tog[ind][i];c[to]w3[ind][to] * c[ind];//将index权值传播给下一个节点}}//将下一层节点所有入度-1for (int i0;ig[ind].size();i) {int tog[ind][i];indeg[to]-1;if(indeg[to]0){q.push(to); //入度为0添加到输出}}}int flag0;//如果输出层都0就输出NULLfor(int i1;in;i){if(outdeg[i]) continue; //出度不为0 过if(c[i]0) continue; //未被激活 过cout i c[i]endl;flag1;}if(flag0) cout NULL endl;}python #!/usr/bin/env python3
# -*- coding: utf-8 -*-MAX_N 100c [0] * (MAX_N 5)
u [0] * (MAX_N 5)
w3 [[0] * (MAX_N 5) for _ in range(MAX_N 5)] # wij
g [[] for _ in range(MAX_N 5)]
outdeg [0] * (MAX_N 5)
indeg [0] * (MAX_N 5)def acm_1_14_dp_shenjingwangluo_test():n, p map(int, input().split())for i in range(1, n 1):c[i], u[i] map(int, input().split())if c[i] 0:c[i] -u[i]for i in range(p):a, b, w map(int, input().split())w3[a][b] w # w3[i][j]indeg[b] 1 # 入度 1outdeg[a] 1 # 出度 1g[a].append(b) q []for i in range(1, n 1):if indeg[i]:continueq.append(i)while q:ind q.pop(0) if c[ind] 0: for i in range(len(g[ind])):to g[ind][i]c[to] w3[ind][to] * c[ind]for i in range(len(g[ind])):to g[ind][i]indeg[to] - 1if indeg[to] 0:q.append(to) flag 0for i in range(1, n 1):if outdeg[i]:continueif c[i] 0:continueprint(f{i} {c[i]})flag 1if not flag:print(NULL)acm_1_14_dp_shenjingwangluo_test() 洛谷1044栈 1到n的栈的输出所有可能 定义递归状态 f[n]代表n个的合法方案数 推导递推公式 分割出战数字结尾为n到1的方案的数量然后加起来结果为f[n]总和 最后一个出栈数字为x的时候条件 小于x的数字进行入栈出栈所有小于x的数字在x入栈之前出完栈x一直在栈底比x大的数字一直入栈出栈 当x作为结尾的方案总数为f(x-1) * f(n-x) :小于x的方案数量乘上大于x的方案数量 写代码 //
// Created by cry on 2024/3/28.
//
#include iostream
using namespace std;
#define MAX_N 18
int f_zhan[MAX_N5];
void acm_1_14_dp_zhan_test(){int n;cin n;f_zhan[0]1;for (int i1;in;i) {f_zhan[i]0;for(int x1;xi;x){f_zhan[i]f_zhan[x-1]*f_zhan[i-x];}}cout f_zhan[n]endl;
}
int main(){acm_1_14_dp_zhan_test();return 0;
}python def zhan():nint(input())f[0]*20f[0]1for i in range(1,n1):f[i]0for x in range(1,i1):f[i]f[x-1]*f[i-x]print(f[n])
zhan()洛谷1050 循环 打表 输出y值 //
// Created by cry on 2024/3/28.
//
#include iostream
#include string
#include vectorusing namespace std;
//大整数
class BigInt:public vectorint{
public:
// 构造函数BigInt(){push_back(0);}BigInt(int n,int v):vectorint(n,v){}BigInt(int x){push_back(x);process_digit();return;
}BigInt(string s,int k) {for(int i0,js.size()-1;ik;i,j--){push_back(s[j]-0);}return ;
}BigInt operator*(const BigInt a){BigInt ret(min(MaxLen,int(size()a.size()-1)),0);for(int i0;isize();i){for(int j0;ja.size();j){if(ij MaxLen)continue; //超过最大长度ret[ij]at(i)*a[j];}}ret.process_digit();return ret;}BigInt operator *(int x){for(int i0;isize();i)at(i)*x;process_digit();return *this;
}static int MaxLen;private:void process_digit(){ //进位for(int i0;isize();i){if(at(i)10)continue;if(i1MaxLen) {if (i 1 size()) push_back(0);at(i 1) at(i) / 10;}at(i) % 10;}return ;
}
};int BigInt::MaxLen0;
ostream operator(ostream out,const BigInt a){for(int ia.size()-1;i0;--i){out a[i];}return out;
}
int acm_1_14_dp_xunhuan_test(){string s;int k;cin sk;BigInt::MaxLenk;BigInt n(s,k);BigInt pre_yn,y;vectorint arr;for(int i0;in.size();i){ypre_y;int cnt1;while((y*n).at(i)!n[i]){yy*pre_y;cnt1;if(cnt 11)break; //当前位置不存在循环节}if(cnt 11){cout -1 endl;return 0;}arr.push_back(cnt);pre_yy;}BigInt ans1;for(int i0;iarr.size();i){ans * arr[i];}cout ans endl;return 0;
}
int main() {acm_1_14_dp_xunhuan_test();return 0;
}
//32 2
//4at(i) % 10;}return ;
}
};int BigInt::MaxLen0;
ostream operator(ostream out,const BigInt a){for(int ia.size()-1;i0;--i){out a[i];}return out;
}
int acm_1_14_dp_xunhuan_test(){string s;int k;cin sk;BigInt::MaxLenk;BigInt n(s,k);BigInt pre_yn,y;vectorint arr;for(int i0;in.size();i){ypre_y;int cnt1;while((y*n).at(i)!n[i]){yy*pre_y;cnt1;if(cnt 11)break; //当前位置不存在循环节}if(cnt 11){cout -1 endl;return 0;}arr.push_back(cnt);pre_yy;}BigInt ans1;for(int i0;iarr.size();i){ans * arr[i];}cout ans endl;return 0;
}
int main() {acm_1_14_dp_xunhuan_test();return 0;
}
//32 2
//4
