学步园

解题思路：预先把一行中，合法（不出现”11“）的状态S1算出来，再在此基础上，将该合法状态，
与其他合法状态互溶的状态S2算出来，放在该状态后面，之后，dp每一行进行状态转移：dp[i][S1]=val[S1]+sum{dp[i-1][S2]};

#include<stdio.h>
#include<vector>
#include<iostream>
using namespace std;
vector<int>rem[16][1600];
int cntrem[16];
int map[16][16];
int val[32868];
int dp[2][32868];
void inite()
{
    int i,up,temp,cas,j;
    for(cas=3;cas<=15;cas++){
        cntrem[cas]=0;
        up=1<<cas;
        for(i=0;i<up;i++){
            temp=i;
            while(temp){
                if((temp&3)==3)break;
                temp>>=1;
            }
            if(temp)continue;
            ++cntrem[cas];
            rem[cas][cntrem[cas]].clear();
            rem[cas][cntrem[cas]].push_back(i);
        }
        for(i=1;i<cntrem[cas];i++){
            for(j=i+1;j<=cntrem[cas];j++){
                if(rem[cas][i][0]&rem[cas][j][0])continue;
                temp=rem[cas][i][0]|rem[cas][j][0];
                while(temp){
                    if((temp&3)==3)break;
                    temp>>=1;
                }
                if(temp)continue;
                rem[cas][i].push_back(rem[cas][j][0]);
                rem[cas][j].push_back(rem[cas][i][0]);
            }
        }
    }
}
int main()
{
    int cnt,i,j,t,now,pre,m,k,ans,temp;
    char ch;
    freopen("in.txt","r",stdin);
    inite();
    while(~scanf("%d%c",&map[1][1],&ch))
    {
        if(ch!='\n')
        {
            cnt=1;
            while(scanf("%d%c",&map[1][++cnt],&ch)&&(ch!='\n'));
            for(i=2;i<=cnt;i++){
                for(j=1;j<=cnt;j++)
                    scanf("%d%c",&map[i][j],&ch);
            }
            for(j=1;j<=cntrem[cnt];j++){
                temp=rem[cnt][j][0];
                val[rem[cnt][j][0]]=0;
                t=1;
                while(temp){
                    if(temp&1)
                        val[rem[cnt][j][0]]+=map[1][t];
                    temp>>=1;
                    t++;
                }
            }
            pre=1,now=0;
            for(i=1;i<=cntrem[cnt];i++)
                dp[pre][rem[cnt][i][0]]=val[rem[cnt][i][0]];
            for(i=2;i<=cnt;i++,pre=!pre,now=!now)
            {
                for(j=1;j<=cntrem[cnt];j++)
                {
                    temp=rem[cnt][j][0];
                    val[rem[cnt][j][0]]=0;
                    t=1;
                    while(temp)
                    {
                        if(temp&1)
                            val[rem[cnt][j][0]]+=map[i][t];
                        temp>>=1;
                        t++;
                    }
                }
                for(j=1;j<=cntrem[cnt];j++)
                {
                    m = rem[cnt][j].size();
                    dp[now][rem[cnt][j][0]] = val[rem[cnt][j][0]];
                    temp = 0;
                    for(k=1;k<m;k++){
                        if(dp[pre][rem[cnt][j][k]]>temp)temp=dp[pre][rem[cnt][j][k]];
                    }
                        dp[now][rem[cnt][j][0]]+=temp;
                }
            }
            ans=0;
            for(i=1;i<=cntrem[cnt];i++){
                if(dp[pre][rem[cnt][i][0]]>ans)ans=dp[pre][rem[cnt][i][0]];
            }
            printf("%d\n",ans);
        }
        else
            printf("%d\n",map[1][1]);
        scanf("%c",&ch);
    }
    return 0;
}