蒟蒻求助!!

P2704 [NOI2001] 炮兵阵地

天南月 @ 2019-06-25 21:16:20

#include<iostream>
#include<math.h>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int n,m;
int F[105],gs[70];
int dp[105][70][70];
int s[70];
map<char,int>p;
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    char ch;
    p['P']=1;
    p['H']=0;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>ch;
            F[i]=(F[i]<<1)+p[ch];
        }
    }
    int len=0,ma=0,maxn=(1<<m);
    for(int i=0;i<maxn;++i)
        if((!(i&(i<<2)))&&(!(i&(i<<1)))){   
            s[++len]=i;
            int l=i;
            while(l){
                gs[len]+=(l&1);
                l>>=1;
            }
        }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=len;++j)
                for(int z=1;z<=len;++z)
                        for(int k=1;k<=len;++k)
        if(((s[k]&F[i])==s[k])&&(!(s[k]&s[z]))&&(!(s[k]&s[j]))&&(!(s[j]&s[z])))
                        dp[i][j][z]=max(dp[i][j][z],dp[i-1][z][k]+gs[j]);
    }
    for(int i=1;i<=len;++i)
        for(int j=1;j<=len;++j)
            ans=max(ans,dp[n][i][j]);
    cout<<ans;
    return 0;
}

by 天南月 @ 2019-06-25 21:31:09

此帖完结


by LJB00131 @ 2019-06-25 21:44:52

说起来map有log的复杂度,不要乱用


by LJB00131 @ 2019-06-25 21:46:39

@wy99804496


by disangan233 @ 2019-06-25 21:49:39

@LJB00131 Orz 您会map


by LJB00131 @ 2019-06-25 21:52:16

@disangan233

没怎么用过。。。


by LJB00131 @ 2019-06-25 21:53:08

我弱啊


by jiangby @ 2019-06-25 22:11:20

@disangan233 orz


by 天南月 @ 2019-06-26 09:09:12

@LJB00131 只有俩元素没有问题吧?


|