纯递推啊~~

其实数论的比dp的成分多

于是dfs也好过

var

n,k,i,j,m:longint;

f:array[0..200,0..6]of longint;

begin

readln(n,k);

for i:=1 to n do

f:=1;

//f[0,0]:=1;

for j:=2 to k do

for i:=j to n do

if i-j>=0 then

f:=f+f;

writeln(f[n,k]);

end.

或或或或或或或或或或或或或或或或或或或或或或或或

var

n,k,i,j,m:longint;

f:array[0..200,0..6]of longint;

begin

readln(n,k);

//for i:=1 to n do

//f:=1;

f[0,0]:=1;

for j:=1 to k do

for i:=j to n do

if i-j>=0 then

f:=f+f;

writeln(f[n,k]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我是用最暴力的3维DP来做的..

for(i=1;i

program datadivide;

var s:array[0..300]of byte;

n,k:byte;

sum:longint;

procedure search(a:byte);

var i:byte;

begin

if a>k then begin

if n=0 then inc(sum);

end

else if a=k then begin

s[a]:=n;

if s[a]>=s[a-1] then begin

dec(n,n);

search(a+1);

inc(n,s[a]);

end

else exit;

end

else if a=1 then begin

for i:=s[a-1] to n div k do begin

s[a]:=i;

dec(n,i);

search(a+1);

inc(n,i);

end;

end

else begin

for i:=s[a-1] to n do begin

s[a]:=i;

dec(n,i);

search(a+1);

inc(n,i);

end;

end;

end;

begin

readln(n,k);

fillchar(s,sizeof(s),0);

sum:=0;

s[0]:=1;

search(1);

writeln(sum);

end.

题解 http://254117343.blog.163.com/

program P1117;

var k,n,m,i,c,z:longint;

procedure find(x,y:longint);

var l:longint;

begin

c:=c+1;

if (c+1=k)and(x=2*l then inc(z)

end

else for l:=x to n div 2 do find(l,y-l);

c:=c-1;

end;

begin

readln(n,k);

if k=2 then writeln(n div 2)

else begin

c:=1;

m:=n;

z:=0;

for i:=1 to n div 2 do find(i,m-i);

writeln(z);

end;

end.

不用数组

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

begin

read(n,k);

f[0,0]:=1;

for i:=1 to n do

for j:=1 to k do

if i-j>=0 then

f:=f+f;

writeln(f[n,k]);

end.

递推。

easy

我怀疑此题考数论比考DP多，

http://blog.sina.com.cn/s/blog\_618b6ea70100ehbg.html~type=v5\_one&label=rela_nextarticle

这个题解确实很好……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 228ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：228ms

var n,k,w:longint;

procedure zhao(dep,cost,last:longint);

var i:longint;

begin

if dep>k then inc(w)

else

begin

if (dep=k)and(n-cost>=last) then zhao(dep+1,n,n-cost)

else if dep

水题~

f=f+f;

例如 7,3

=1+1+5=1+2+4=1+3+3

=2+2+3

前3种就是f[6,2]

后一种可以看成 (1,1,1)+(1,1,2)即 f[4,3]

秒杀

初始f[0,0]=1;

whyvine的解题报告：

http://blog.sina.com.cn/s/blog\_618b6ea70100ehbg.html~type=v5\_one&label=rela_nextarticle

我感觉楼下的各位没有一位讲的特别透彻，对于大牛似乎很容易理解，但到底方程是怎么想出来的，菜鸟们还是看看whyvine的解题报告吧。

这是组合数学的经典问题。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms

搜索+剪枝=AC=秒杀！

O(∩_∩)O哈哈~

程序没有新意，把问题转化成了有N个正方体，排成K列，而且要按递增的顺序就不会出现重复的情况去理解，可能比较好做

Program P1117;

var f:array[0..400,0..10] of longint;

i,j,n,m,k:longint;

Begin

readln(n,m);

fillchar(f,sizeof(f),0);

f[0,0]:=1;

for i:=1 to n do

for j:=1 to m do

if i>=j then f:=f+f;

writeln(f[n,m]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

n,k,t:longint;

a:array[-2..10] of integer;

procedure try(x,s,m:longint);

var i:integer;

begin

if x=k then

begin

t:=t+1;

exit;

end;

for i:=a[x-1] to (s div m) do

begin

a[x]:=i;

try(x+1,s-a[x],m-1);

end

end;

begin

readln(n,k);

a[0]:=1;

try(1,n,k);

write(t);

end.

搜?

var

f:array[-1..400,-1..100]of longint;

n,k:longint;

procedure init;

begin

readln(n,k);

end;

procedure dp;

var

i,j,l:longint;

begin

f[0][0]:=1;

for i:=1 to n-1 do

for j:=0 to n-i do

for l:=0 to k-1 do

if f[j][l]>0 then inc(f[j+i][l+1],f[j][l]);

writeln(f[n][k]);

end;

begin

init;

dp;

end.

简单dp

把这两位的顶上来，综合下！

把7分为3份 有4种分法 这个是样例

可分为1 1 5 1 2 4 1 3 3 2 2 3

而1 1 5 1 2 4 1 3 3又可以看作

15 24 33 +1

223 可以看作 1 1 2 +1 1 1

那就是a[7,3]:=a[7-1,3-1]+a[7-3,3]

状态转移方程：a:=a+a

因为是不要重的 所以就把方程做的条件设为 i>=j

a[0,0]:=1

对于f[ i ][ j ],表示i个数分j份不重复的方法数

有人问是怎么想到的……因为针对1做dp，可以避免重复问题

f[ i ][ j ] = f[ i-1 ][ j-1 ]+f[ i-j ][ j ];

f[ i-1 ][ j-1 ]表示的是每当首位为1的时候，也就是第一位只是1，所以剩下了i-1个数，而且除了第一部分外共有j-1份，也就是说第一部分为1的种数就是余下的数分成j-1份的方法数

当首位不为1的时候呢，同样避免重复问题，如果分j份，每份的数减1，这样依次就又退化成了首位为1的问题，从而可以利用递推求解。

#include

main()

{

int f[201][7]={1},n,k,i,j;

scanf("%d%d",&n,&k);

for(i=1;i

//求n的k部分拆

//分两种情况讨论:

//1:第一位是1,那么可以看作n-1个数分成k-1个部分的可能数

//2:第一位不是1,那么将每一位减1,n-k,将n-k分成k个部分

var

f:array[0..200,0..200]of longint;

n,k,i,j:longint;

begin //main

readln(n,k);

f[1,1]:=1;

for i:=2 to n do

for j:=1 to i do

f:=f+f;

writeln(f[n,k]);

end.