QBSELECT - VOI06 Chọn ô
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<vector>
#define MAX 10101
using namespace std;
int a[4][MAX];
int f[17][MAX];
vector<int> v[17];
int n;
int res;
const int INF=-2e9;
void init(void) {
int i,j;
scanf("%d",&n);
for (i=0;i<4;i=i+1)
for (j=1;j<=n;j=j+1)
scanf("%d",&a[i][j]);
}
bool fit(int s1,int s2) {
int i;
for (i=0;i<3;i=i+1) {
if (((s1|(1<<i))==s1) && ((s1|(1<<(i+1)))==s1)) return (false);
if (((s2|(1<<i))==s2) && ((s2|(1<<(i+1)))==s2)) return (false);
}
for (i=0;i<4;i=i+1)
if (((s1|(1<<i))==s1) && ((s2|(1<<i))==s2)) return (false);
return (true);
}
void gens(void) {
int i,j;
for (i=0;i<16;i=i+1)
for (j=0;j<16;j=j+1)
if (fit(i,j)) v[i].push_back(j);
}
void optimize(void) {
res=INF;
int i,j,k,l;
for (i=0;i<4;i=i+1)
for (j=1;j<=n;j=j+1)
if (a[i][j]>res) res=a[i][j];
if (res<=0) {
printf("%d",res);
return;
}
for (i=0;i<16;i=i+1)
for (j=1;j<=n;j=j+1)
f[i][j]=INF;
for (i=0;i<v[0].size();i=i+1){
f[v[0][i]][1]=0;
for (j=0;j<4;j=j+1)
f[v[0][i]][1]+=a[j][1]*((v[0][i]|(1<<j))==v[0][i]);
}
for (j=2;j<=n;j=j+1)
for (i=0;i<16;i=i+1) {
if (v[i].size()<1) continue;
for (k=0;k<v[i].size();k=k+1)
if (f[v[i][k]][j-1]>f[i][j]) f[i][j]=f[v[i][k]][j-1];
for (l=0;l<4;l=l+1)
f[i][j]+=a[l][j]*((i|(1<<l))==i);
}
res=INF;
for (i=0;i<16;i=i+1)
if ((n!=1) || (i!=0))
if (res<f[i][n]) res=f[i][n];
printf("%d",res);
}
int main(void) {
init();
gens();
optimize();
return 0;
}