状压DP uvalive 6560

// 状压DP uvalive 6560
// 题意：相邻格子之间可以合并，合并后的格子的值是之前两个格子的乘积，没有合并的为0，求最大价值
// 思路：
// dp[i][j]：第i行j状态下的值
// j：0表示不合并，1表示向下合并
// 一开始输入要修改一下，然后滚动数组优化

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
#define LL long long
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 1020;
const int maxx = 200010; 
#define clc(a,b) memset(a,b,sizeof(a))
const double eps = 0.025;
void fre() {freopen("in.txt","r",stdin);}
void freout() {freopen("out.txt","w",stdout);}
inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}

int n;
int g[N][3];
int dp[2][10];
bool check(int u,int f){
    for(int i=0;i<3;i++){
        if(u&(1<<i)&&f&(1<<i)) return false;
    }
    return true;
}

int cal(int r,int u,int f){
    int ans=0;
    for(int i=0;i<3;i++){
        if(f&(1<<i)) ans+=g[r][i]*g[r-1][i];
    }
    int t=u|f;
    int tem1=0,tem2=0;
    if(!(t&1)&&!(t&2)) tem1=g[r][0]*g[r][1];
    if(!(t&2)&&!(t&4)) tem2=g[r][1]*g[r][2];
    ans+=max(tem1,tem2);
    return ans;
}
int main(){
    int cas=1;
    while(~scanf("%d",&n),n){
        for(int i=0;i<3;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&g[j][i]);
            }
        }
        memset(dp[0],0,sizeof(dp[0]));
        int p=0;
        int ans=-inf;
        for(int i=1;i<=n;i++){
            int pre=p;
            p=p^1;
            memset(dp[p],0,sizeof(dp[p]));
            for(int j=0;j<8;j++){
                for(int k=0;k<8;k++){
                    if(check(j,k)){
                        dp[p][j]=max(dp[p][j],dp[pre][k]+cal(i,j,k));
                    }
                }
                if(i==n){
                    ans=max(ans,dp[p][j]);
                }
            }
        }
        printf("Case %d: ",cas++);
        printf("%d
",ans);
    }
    return 0;
}