第三周题单

互不侵犯KING

思路：dp[i][j][k]表示前i行，且已经用了j个国王，且第i行的摆放状态为k（二进制）；

dp[i][j][k]=dp[i-1][ j-num[now]][pre]，now表示第i行的状态，pre表示上一行的状态，num[i]维护一行的状态为i的国王数量，且需保证now和pre满足为相邻行的条件

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=600+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};

int n,k,num[N],ok[N];
int dp[10][N][N];
void init(){
    for(int i=0;i<(1<<n);++i){
        if(!(i&(i<<1))){
            ok[i]=true;
            int t=i;
            while(t){
                num[i]+=(t&1);
                t>>=1;
            }
            dp[1][num[i]][i]=1;
        }
    }
}
void solve(){
    cin>>n>>k;
    init();
    for(int i=2;i<=n;++i)
        for(int j=0;j<=k;++j)
            for(int now=0;now<(1<<n);++now){
                if(!ok[now]||num[now]>j)continue;
                for(int pre=0;pre<(1<<n);++pre){
                    if(!ok[pre]||num[pre]>(j-num[now]))continue;
                    if((pre&now)||(pre&(now<<1))||(pre&(now>>1)))continue;
                    dp[i][j][now]+=dp[i-1][j-num[now]][pre];
                }
            }
    int ans=0;
    for(int i=0;i<(1<<n);++i){
        ans+=dp[n][k][i];
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;

    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

 炮兵阵地

思路：dp[i][j][k]表示前i行的状态，且第i行的状态为ok[j]，第i-1的状态为ok[k]，枚举i、i-1、i-2行的状态j1、j2、j3，满足相邻行的条件且放大炮的位置不是山地即更新 dp[i][j1][j2]=max（dp[i][j1][j2]，dp[i-1][j2][j3]）；

初始时预处理好一行中存在的所有放炮的可行情况，用ok存；并且用mp存山地的位置

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=100+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};

int n,m,num[N],ok[N];
int dp[N][N][N];
int mp[N];
void init(){

}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        string s;cin>>s;
        for(int j=0;j<m;++j){
            if(s[j]=='H')mp[i]|=(1<<j);
        }
    }
    int cnt=0;
    auto count=[](int x){
        int sum=0;
        while(x){
            if(x&1)sum++;
            x>>=1;
        }
        return sum;
    };
    for(int i=0;i<(1<<m);++i){
        if(!(i&(i<<2))&&!(i&(i<<1))){
            num[cnt]=count(i);
            ok[cnt++]=i;
        }
    }
    for(int i=0;i<cnt;++i){
        if(!(mp[1]&ok[i])){
            dp[1][i][0]=num[i];
        }
    }
    for(int i=2;i<=n;++i){
        for(int j1=0;j1<cnt;++j1){
            if(ok[j1]&mp[i])continue;
            for(int j2=0;j2<cnt;++j2){
                if(ok[j2]&mp[i-1]||ok[j2]&ok[j1])continue;
                for(int j3=0;j3<cnt;++j3){
                    if((ok[j3]&mp[i-2])||(ok[j3]&ok[j2])||(ok[j3]&ok[j1]))continue;
                    dp[i][j1][j2]=max(dp[i][j1][j2],dp[i-1][j2][j3]+num[j1]);
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<cnt;++i)
        for(int j=0;j<cnt;++j)ans=max(dp[n][i][j],ans);
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;

    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}