Code: Select all
nway(n, s, pdl) = nway(n-1, s, 0) + nway(n-1, s-1, 1) if pdl=1
= nway(n-1, s, 0) + nway(n-1, s, 1) if pdl =0
n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)f74956227 wrote:
i finally got ac but i think the recursive function of the DP is
n(a,b,1)=n(a-1,b-1,1)+n(a-1,b-1,0)
n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)
a is the number of drawer and b is the secured-num and the 0 or 1 means that the situation of the top drawer.
Finally thank all of you^^
. please helpCode: Select all
#include<stdio.h>
#include<math.h>
unsigned long long int secureit(int n,int s);
unsigned long long int soln_lck_fst_it(int n,int s);
unsigned long long int secure[100][100];
unsigned long long int soln_lck_fst[100][100];
int main()
{
int n,s;
unsigned long long int ans;
while(1)
{
int i,j;
scanf("%d %d",&n,&s);
if(n<0 && s<0) break;
for(i=0;i<100;i++)
for(j=0;j<100;j++) secure[i][j]=-1;
for(i=0;i<100;i++)
for(j=0;j<100;j++) soln_lck_fst[i][j]=-1;
ans=secureit(n,s);
printf("%llu\n",ans);
}
return 0;
}
unsigned long long int soln_lck_fst_it(int n,int s)
{
if(s==n || s==n-1) return 1;
if(n==2 && s==1) return 1;
if(n==2 && (s==1 || s==2)) return 1;
if(s>n) return 0;
if(soln_lck_fst[n][s]!=-1) return soln_lck_fst[n][s];
if(s==1)
{
soln_lck_fst[n][s]=(unsigned long long int) pow(2,n-2) - ((n-2)*(n-3))/2;
return soln_lck_fst[n][s];
}
soln_lck_fst[n][s]=secureit(n-1,s-1);
return soln_lck_fst[n][s];
}
unsigned long long int secureit(int n,int s)
{
if(s==n || s==n-1) return 1;
if(n==2 && s==1) return 1;
if(n==2 && (s==1 || s==2)) return 1;
if(s>n) return 0;
if(secure[n][s]!=-1) return secure[n][s];
secure[n][s]=soln_lck_fst_it(n,s)+secureit(n-1,s)-soln_lck_fst_it(n-1,s)+soln_lck_fst_it(n-1,s+1);
return secure[n][s];
}
Code: Select all
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int ll;
ll memo[75][75][75];
ll n,s;
ll LockDrawer(ll lst,ll id,ll nlck){
if(id==n){
if(nlck==s) return 1;
else return 0;
}
if(memo[lst][id][nlck]!=-1) return memo[lst][id][nlck];
ll tmp=0;
if(lst==0){
tmp=LockDrawer(lst,id+1,nlck)+LockDrawer(1,id+1,nlck);
}
else{
tmp=LockDrawer(lst,id+1,nlck+1)+LockDrawer(0,id+1,nlck);
}
return memo[lst][id][nlck]=tmp;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%lld %lld",&n,&s)){
if(n<0&&s<0) break;
for(ll i=0;i<66;i++)
for(ll j=0;j<66;j++)
for(ll k=0;k<66;k++)
memo[i][j][k]=-1;
if(s>n) printf("0\n");
else printf("%lld\n",LockDrawer(1,0,0));
}
}