VKNIGHTS - Quân mã
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 111
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
int f[70][maxn],C[70][maxn],n,a[maxn],the,A,B,so,m,r0[5],r1[5],r2[5],KQ=0,KQ1 = 0;
int main(){
// freopen("VKNIGHTS.in","r",stdin);
scanf("%d",&n);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
if(n==1){
printf("%d 1",3-(a[1]!=0));
return 0;
}
memset(f,0,sizeof(f));
memset(C,0,sizeof(C));
for(int i = 0;i<8;i++){
the = i;
so = 0;
for(int t= 1;t<=3;t++){
r0[t] = the%2;
the/=2;
so+=r0[t];
}
if(!r0[a[1]]){
f[i][0] = so;
C[i][0] = 1;
}
// printf("%d\n",f[i][0]);
}
for(int i = 1;i<n;i++){
for(int j = 0;j<1<<6;j++){
A = j/8; m = A;
B = j%8;
so = 0;
//printf("%d %d %d %d\n",i,j,A,B);
for(int t = 1;t<=3;t++){
r1[t] = A%2;
r2[t] = B%2;
A/=2;
B/=2;
if(r2[t]) so++;
}
if(r1[a[i]] || r2[a[i+1]] || (r1[1]&&r2[3])||(r1[3]&&r2[1]))
continue;
for(int k = 0;k<8;k++){
the = k;
for(int t= 1;t<=3;t++){
r0[t] = the%2;
the/=2;
}
if((r0[1]&&r1[3])||(r0[3]&&r1[1])||(r0[1]&&r2[2])||(r0[3]&&r2[2])||(r0[2]&&r2[1])||(r0[2]&&r2[3]))
continue;
if(f[j][i] < f[k*8+m][i-1]+so){
f[j][i] = f[k*8+m][i-1]+so;
C[j][i] = C[k*8+m][i-1];
}
else if(f[j][i] == f[k*8+m][i-1]+so) C[j][i] += C[k*8+m][i-1];
}
if(i==n-1){
if(KQ <= f[j][i]){
if(KQ<f[j][i]) KQ1 = C[j][i];
else KQ1 += C[j][i];
KQ = f[j][i];
}
}
//printf("%d %d",i,j,f[i][j]);
}
}
printf("%d %d",KQ,KQ1);
// getch();
}