#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 16,M=9;
const double INF = 1e9;

int n;
double X;
int s[M][M];
double dp[M][M][M][M][N];

double get(int x1,int y1,int x2,int y2)
{
    double sum = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
    sum-=X;
    return sum*sum/n;

}

double find(int x1,int y1, int x2 ,int y2, int k)
{
    double &v = dp[x1][y1][x2][y2][k];

    if(v>=0) return v;
    if(k==1) return v = get(x1,y1,x2,y2);
    v=INF;

    for(int i = x1 ; i < x2 ; i ++)
    {
        v = min(v,get(x1,y1,i,y2)+find(i+1,y1,x2,y2,k-1));
        v = min(v,get(i+1,y1,x2,y2)+find(x1,y1,i,y2,k-1));
    }

    for(int i = y1 ; i < y2 ; i ++)
    {
        v = min(v,get(x1,y1,x2,i)+find(x1,i+1,x2,y2,k-1));
        v = min(v,get(x1,i+1,x2,y2)+find(x1,y1,x2,i,k-1));
    }

    return v;
}

int main()
{
    cin>>n;

    for(int i = 1 ; i < 9 ; i ++)
        for(int j = 1 ; j < 9 ; j ++)
        {
            cin>>s[i][j];
             s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }

    X = (double)s[8][8]/n;
    memset(dp,-1,sizeof dp);
    printf("%.3lf\n",sqrt(find(1,1,8,8,n)));

    return 0;

}

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 53, M = 30;;

typedef long long LL;

int n;
int w[N];
int dp[N][N][M];

void add(int a[] ,int b[])
{
    static int c[M];
    memset(c,0,sizeof c);
    int t = 0;
    for(int i = 0 ; i < M ; i ++)
    {
        t+=a[i]+b[i];
        c[i]=t%10;
        t/=10;
    }
    memcpy(a,c,sizeof c);
}

void mul(int a[] , LL b)
{
    static int c[M];
    memset(c,0,sizeof c);
    LL t = 0;
    for(int i = 0 ; i < M ; i ++)
    {
        t+=(LL)(a[i]*b);
        c[i]=t%10;
        t/=10;
    }

    memcpy(a,c,sizeof c);
}

int cmp(int a[] , int b[])
{
    for(int i = M - 1 ; ~i ; i--)
    {
        if(a[i]>b[i]) return 1;
        if(a[i]<b[i]) return -1;
    }
    return 0;
}

void print(int a[])
{
    int k = M - 1;
    while(k&&a[k]==0) k--;
    while(k>=0) cout<<a[k--];
    cout<<endl;
}

int main()
{
    cin>>n;
    for(int i = 1 ; i <= n ; i ++)
        cin>>w[i];

    int sum[M];
    for(int len = 3; len <= n ; len ++)
        for(int l = 1 ; l + len - 1 <= n ; l ++)
        {

            int r = l + len - 1;
            dp[l][r][M-1]=1;
            for(int k = l + 1; k < r ; k ++ )
            {
                memset(sum,0,sizeof sum);
                sum[0] = w[l];
                mul(sum,w[r]);
                mul(sum,w[k]);
                add(sum,dp[l][k]);
                add(sum,dp[k][r]);
                if(cmp(dp[l][r],sum) > 0)
                    memcpy(dp[l][r],sum,sizeof sum);
            }

        }

    print(dp[1][n]);

    return 0;
}

#include<iostream>

using namespace std;

const int N = 31;

int w[N];
int dp[N][N];
int g[N][N];
int n;

void dfs(int l , int r)
{
    if(l>r) return ;

    int root = g[l][r];
    cout << root<<' ';
    dfs(l,root-1);
    dfs(root+1,r);
}

int main()
{
    cin>>n;

    for(int i = 1 ; i <= n ; i ++)
        cin>>w[i];

    for(int len =1 ; len <= n ; len ++)
        for(int l = 1 ; l + len - 1 <= n ; l ++)
        {
            int r = l + len - 1;
            if(l == r ) dp[l][r]=w[l] ,g[l][r]= l;
            else
            {
                for(int k = l ; k <= r ; k ++)
                {
                    int left = k == l ? 1 : dp[l][k-1];
                    int right = k == r ? 1 : dp[k+1][r];

                    int score = left * right + w[k];

                    if(dp[l][r] < score)
                    {
                        dp[l][r]=score;
                        g[l][r]=k;
                    }
                }
            }
        }

    cout<<dp[1][n]<<endl;

    dfs(1,n);
    return 0;
}

#include<iostream>

using namespace std;

const int N = 210;

int w[N];
int n;
int dp[N][N];

int main()
{
    cin>>n;  
    for(int i = 1 ; i <= n ; i ++)
    {
        cin>>w[i];
        w[i+n] = w[i];
    }

    for(int len= 1 ; len <= n+1 ; len ++)
        for(int l = 1 ; l + len -1 <= n<<1 ; l ++)
        {
            int r = l + len -1;

            for(int k = l + 1 ;  k < r ; k ++)
                dp[l][r]=max(dp[l][r], dp[l][k]+dp[k][r]+w[k]*w[l]*w[r]);
        }

    int res = 0;
    for(int i =1 ; i <= n ; i ++)
        res = max(res,dp[i][i+n]);

    cout<<res<<endl;

    return 0;
}

#include<cstring>
#include<iostream>

using namespace std;

const int N = 410;

int n,m;
int a[N],s[N];
int ma[N][N],mi[N][N];


int main()
{
    cin>>n;

    for(int i = 1 ; i <= n ; i ++)
    {
        cin>>m;
        a[i]=a[i+n]=m;
    }
    for(int i = 1 ; i <= n<<1 ; i ++)
        s[i]=s[i-1]+a[i];

    memset(ma,-0x3f,sizeof ma);
    memset(mi,0x3f, sizeof mi);

    for(int len = 1 ; len <= n ; len ++)
        for(int l = 1 ; l+len - 1 <= n*2 ; l ++)
        {
            int r = l + len - 1;
            if(l==r) ma[l][l]=mi[l][l]=0;
            else
                for(int k = l ; k < r ; k ++)
                {
                    ma[l][r]=max(ma[l][r],ma[l][k]+ma[k+1][r]+s[r]-s[l-1]);
                    mi[l][r]=min(mi[l][r],mi[l][k]+mi[k+1][r]+s[r]-s[l-1]);
                }
        }
    int resa=-0x3f3f3f3f,resi=0x3f3f3f3f;

    for(int i = 1 ; i <= n ; i ++)
    {
        resa=max(ma[i][i+n-1],resa);
        resi=min(mi[i][i+n-1],resi);
    }

    cout<<resi<<'\n'<<resa<<endl;

    return 0;
}

#include<iostream>
#include<cmath>
#include<cstring>

#define x first
#define y second

using namespace std;

const int N = 18, M = 1 <<18;
const double esc=1e-6;
typedef pair<double,double> PDD;

int path[N][N];
PDD p[N];
int dp[M];
int n,m;
int t;

int cmp(double a , double b)
{
    if(fabs(a-b)<esc) return 0;
    if(a<b) return -1;
    return 1;
}

void solve()
{
    cin>>n>>m;
    memset(path , 0 , sizeof path);
    for(int i = 0 ; i < n ; i ++) cin>>p[i].x>>p[i].y;

    for(int i = 0 ; i < n ; i ++)
    {
        path[i][i] += 1 << i;
        for(int j = 0 ; j < n ; j ++)
        {
            double x1 = p[i].x, y1 = p[i].y;
            double x2 = p[j].x, y2 = p[j].y;

            if(!cmp(x1,x2)) continue;

            double a = (y1/x1 - y2/x2) /(x1-x2);
            double b = (y1/x1-a*x1);

            if(cmp(a,0)>=0) continue;

            int state=0;
            for(int k = 0 ; k < n ; k ++)
            {
                double xx = p[k].x, yy = p[k].y;
                if(!cmp(a*xx*xx+b*xx,yy))
                    state += 1 << k;
            }
            path[i][j] += state;
        }
    }
    memset(dp , 0x3f , sizeof dp);
    dp[0]=0;
    for(int i = 0 ; i + 1 < 1 <<n ; i ++)
    {
        int x = 0;
        for(int j = 0 ; j < n ; j ++ )
            if(!(i>>j&1))
            {
                x = j;
                break;
            }
        for(int j = 0 ; j < n ; j ++)
            dp[i|path[x][j]] = min(dp[i|path[x][j]],dp[i]+1);
        }
    cout<<dp[(1<<n) - 1]<<endl;
}

int main()
{
    cin>>t;
    while(t--)
        solve();

    return 0;
}

dp[i][j][k]: 表示 所有前 $i$ 行 第 $i - 1$ 行状态为 $j$ 第 $i$ 行的状态为 $k$ 的所有炮兵数

#include<vector>
#include<iostream>

using namespace std;

const int N = 110 , M = 1<<11;

int dp[2][M][M];
int n,m;
int g[2000];
vector<int> state;
int cnt[M];

bool check(int x)
{
    for (int i = 0; i < m; i ++ )
        if ((x >> i & 1) && ((x >> i + 1 & 1) || (x >> i + 2 & 1)))
            return false;
    return true;
}

int count(int x)
{
    int res=0;
    while(x)
    {
        if(x&1) res++;
        x>>=1;
    }
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 0 ; j < m ; j ++)
        {
            char c;
            cin>>c;
            if(c=='H')
                g[i]+=1<<j;
        }

    for(int i = 0 ; i < 1 << m ; i ++)
        if(check(i))
        {
            state.push_back(i);
            cnt[i]=count(i);
        }

    for(int i = 1 ; i <= n ; i ++)
        for(int j = 0 ; j < state.size() ; j ++)
            for(int k = 0 ; k < state.size() ; k ++)
                for(int u = 0 ; u < state.size() ; u ++)
                {
                    int a = state[j],b=state[k],c=state[u];
                    if(a & b | a & c | b & c ) continue;
                    if(g[i]&b| g[i-1]&a) continue;

                    dp[i&1][j][k]=max(dp[i&1][j][k],dp[i-1&1][u][j]+cnt[b]);
                }

    int res=0;
    for(int i = 0 ; i < state.size() ; i ++)
        for(int j = 0 ; j < state.size() ; j ++)
            res=max(res,dp[n&1][i][j]);

    cout<<res<<endl;

    return 0;
}

#include<vector>
#include<iostream>

using namespace std;

const int N = 1 << 12,mod = 1e8;

int n,m;
int dp[13][N];
int ma[13][13];
int w[N];
vector<int> state;
vector<int> head[N];

bool check(int x)
{
    if(x&x<<1) return false;
    return true;
}

int main()
{
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 0 ; j < m ; j ++)
        {
            int t;
            cin>>t;
            w[i] += !t * (1 << j) ; 
        }

    for(int i = 0 ; i < 1<<m; i ++)
        if(check(i))
            state.push_back(i);

    for(int a = 0 ; a < state.size() ; a ++)
        for(int b = 0 ; b < state.size() ; b ++)
            if(!(state[a]&state[b]))
                head[a].push_back(b);

    dp[0][0]=1;
    for(int i = 1 ; i <= n + 1 ; i ++ )
        for(int j = 0 ; j < state.size() ; j ++)
            if(!(state[j]&w[i]))
                for(int k :head[j])
                    dp[i][j] = (dp[i][j]+dp[i-1][k])%mod;
    cout<<dp[n+1][0]<<endl;

    return 0;
}