I coded with 8 dimensional ugly memoized solution and got TLE.....how 8 dimension gets AC? or am I missing something
here is my code.
Code: Select all
#include<iostream>
#include<string.h>
#include<algorithm>
#include<numeric>
#include<vector>
using namespace std;
int sum,r,n,N,R,C,t,txt;
typedef vector<int> vi;
typedef long long LL;
LL dp[5][8][8][8][8][8][5][8];
LL doit(int c,int c1,int c2,int c3,int c4,int len,int fc,int flen){
LL &ret=dp[c][c1][c2][c3][c4][len][fc][flen];
if(ret!=-1)return ret;
if(c1==0&&c2==0&&c3==0&&c4==0){
if(c==fc||len==flen)return ret=0;
else return ret=1;
}
ret=0;
vi v(5);v[1]=c1;v[2]=c2;v[3]=c3;v[4]=c4;
for(int i=1;i<=n;i++){
if(!v[i]||i==c)continue;
for(int j=1;j<=v[i]&&j<=3;j++){
if(j==len)continue;
vi vv=v;vv[i]-=j;
if(fc==0)ret+=doit(i,vv[1],vv[2],vv[3],vv[4],j,i,j);
else ret+=doit(i,vv[1],vv[2],vv[3],vv[4],j,fc,flen);
}
}
return ret;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
//freopen("out.txt","r",stdout);
#endif
int i,j,k;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(dp,-1,sizeof(dp));
vi v(5,0);
for(i=1;i<=n;i++)cin>>v[i];
int sum=accumulate(v.begin(),v.end(),0);
if(!sum){printf("1\n");sum=0;continue;}
LL rr=doit(0,v[1],v[2],v[3],v[4],0,0,0);
printf("%lld\n",rr);
}
return 0;
}
thanx in advance.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................