12月将举办首届西电ACM新生赛,敬请期待~~~~
Xidian Online Judge WebBoard
[ New Thread ]
Problem 1002 >> 求教DP为何会超时
17031211702 @ 2017-09-06 18:07:54
[ Quote ] [ Edit ] [ Delete ] 1#
基本上就是从前往后的DP,感觉复杂度够的啊....

#include <stdio.h>

int x,y,z,t;

int max(int a, int b, int c){
int ans=a;
if (b>ans) ans=b;
if (c>ans) ans=c;
return ans;
}

int harm(int n,int a, int b){
if (n==0) return 0;
return max(harm(n-1,a,b)+(t+b*z)*x,harm(n-1,a+1,b),harm(n-1,a,b+1))
+(t+b*z)*a*y;
}

int main(void){
int n;
while (scanf("%d%d%d%d%d",&n,&x,&y,&z,&t)!=EOF) printf("%d",harm(n,0,0));
return 0;
}
17131212946 @ 2017-09-08 01:29:31
[ Quote ] [ Edit ] [ Delete ] 2#
讨论函数 harm(0,a,b) 被调用的次数。

相当于从 (0,0) 出发,每一步可以向上或向右走 1 格,或者不动,n 步后到达 (a,b)
的路径条数。

即,n 步中有 a 步向右, b 步向上, (n-a-b) 步不动,则共有 n!/(a!b!(n-a-b)!)
种路径。

然后对 0 <= a+b <= n 求和。令 C 为组合数,答案是:

C(n, 0) [ C(n,0) + C(n,1) + ... + C(n, n) ] +
C(n, 1) [ C(n-1, 0) + C(n-1, 1) + ... + C(n-1, n-1) ] +
... +
C(n, n-1) [ C(1, 0) + C(1, 1) ] +
C(n, n) C(0, 0)



C(n, 0) 2^n + C(n, 1) 2^(n-1) + ... + C(n, n) 2^0
= C(n, 0) 2^n 1^0 + C(n, 1) 2^(n-1) 1^1 + ... + C(n, n) 2^0 1^n
= (2+1)^n
= 3^n

(其实就是 (x+y+z)^3 展开后所有系数的和啦,令 x=y=z=1 就行了。)

对于函数 harm(x, a, b) 被调用的次数,同理可得,对于特定 x 和所有 a, b ,总
调用次数为 3^(n-x) 。把所有 x 加起来,就是

3^0 + 3^1 + ... + 3^n = 3^(n+1) / 2

对于极限数据

3^(100 + 1) / 2 = 773066281098016996554691694648431909053161283001

这复杂度。。。你也敢写。。。
17131212946 @ 2017-09-08 01:32:25
[ Quote ] [ Edit ] [ Delete ] 3#
(x+y+z)^3 应为 (x+y+z)^n。
[Top] [Previous Page] [Next Page]
Anything about the Problems, Please Contact Admin:admin
All Copyright Reserved 2010-2014 Xidian ACM Online Judge TEAM
GPL2.0 2003-2014 HUSTOJ Project TEAM