【蓝桥】【洛谷】P2563 [AHOI2001]质数和分解(动态规划) |
您所在的位置:网站首页 › 骗术的本质只有三种 › 【蓝桥】【洛谷】P2563 [AHOI2001]质数和分解(动态规划) |
题目链接:https://www.luogu.org/problemnew/show/P2563 题目描述任何大于 1 的自然数 n 都可以写成若干个大于等于 2 且小于等于 n 的质数之和表达式(包括只有一个数构成的和表达式的情况),并且可能有不止一种质数和的形式。例如,9 的质数和表达式就有四种本质不同的形式: 9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7 。 这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。 试编程求解自然数 n 可以写成多少种本质不同的质数和表达式。 输入输出格式输入格式: 文件中的每一行存放一个自然数 n(2 < n < 200) 。
输出格式: 依次输出每一个自然数 n 的本质不同的质数和表达式的数目。 输入样例#1: 2 200
输出样例#1: 1 9845164 稍微分析 状态转移方程: f[j] = f[j] + f[j-prime[i]] 动态规划的题思路每次都不好讲清楚,感觉最重要的还是结合代码和状态转移方程来领悟啊 AC代码 #include using namespace std; int f[201];//记录当前下标n的 本质不同的质数和,初始值全为0 int pri[201];//用来排除非质数,初始值全为0 void add(int x) { //当前不同的质数和f[i]由自身f[i]和i减去一个质数x(f[i-x]) 的 不同的质数和组成 for(int i=x; i |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |