hdu 5389 Zero Escape(记忆化搜索)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #pragma comment(linker, "/STACK:1024000000,1024000000") 6 #define N 100006 7 #define M 16 8 #define MOD 258280327 9 int n,A,B; 10 int dp[N][M]; 11 int a[N]; 12 int sum; 13 int dfs(int cur,int suma,int now) 14 { 15 if(dp[cur][suma]!=-1) return dp[cur][suma]; 16 if(cur>n) 17 { 18 if(now==0) 19 { 20 return (sum-now)%9==B; 21 } 22 if(now==sum) 23 { 24 return suma == A; 25 } 26 return suma==A && (sum-now)%9==B; 27 } 28 29 dp[cur][suma]=dfs(cur+1,(suma+a[cur])%9,now+a[cur])+dfs(cur+1,suma,now); 30 return dp[cur][suma]%=MOD; 31 } 32 int main() 33 { 34 int t; 35 scanf("%d",&t); 36 while(t--) 37 { 38 scanf("%d%d%d",&n,&A,&B); 39 if(A==9) 40 A=0; 41 if(B==9) 42 B=0; 43 sum=0; 44 for(int i=1;i<=n;i++) 45 { 46 scanf("%d",&a[i]); 47 sum+=a[i]; 48 } 49 50 memset(dp,-1,sizeof(dp)); 51 printf("%d\n",dfs(1,0,0)); 52 } 53 return 0; 54 }View Code
优质内容筛选与推荐>>