首页 > 代码库 > 【省选水题集Day1】一起来AK水题吧! 题解(更新到A)
【省选水题集Day1】一起来AK水题吧! 题解(更新到A)
题目:http://www.cnblogs.com/ljc20020730/p/6937936.html
水题A:[AHOI2001]质数和分解
安徽省选OI原题!简单Dp。
一看就是完全背包求方案数!
完全背包都会打吧,原来是最优值,现在是累计值。
状态转移方程:f[j]=f[j]+f[j-w[i]],w[i]是待选质数。
理解:一个数要拆成若干素数和,等同于拆成所有该数减去一个素数差的方案数之和(而不是最优方案数)
但这么做需要初始化为0,同时用滚动数组可以减小时间和空间复杂度。
代码如下:(懒得打筛法求素数了)
const maxn=200; var w,f:array[0..1000000]of longint; u:array[1..1000000]of boolean; i,j,x,t:longint; begin w[1]:=2; fillchar(u,sizeof(u),true); inc(t); for i:=3 to maxn do begin for j:=2 to (i div 2)do if i mod j=0 then begin u[i]:=false; break;end; if u[i] then begin inc(t); w[t]:=i;end; end; f[0]:=1; for i:=1 to t do for j:=w[i] to maxn do f[j]:=f[j]+f[j-w[i]]; while not eof do begin readln(x); writeln(f[x]); end; end.
2017-6-3 更新
【省选水题集Day1】一起来AK水题吧! 题解(更新到A)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。