0分求助

P2704 [NOI2001] 炮兵阵地

nuo0930 @ 2020-06-21 10:16:53

蒟蒻初学状压dp,样例都没有过

#include<iostream>
using namespace std;
int tot(int x) {
    int ans=0;
    while(x&1) {
        ans++;
        x>>=1;
    }
    return ans;
}
int dp[4][61][61];
int main() {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int s[61];
    int t[61];
    int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=0; i<1<<m; i++)
        if(!(i&(i<<1))&&!(i&(i<<2))) {
            s[++cnt]=i;
            t[cnt]=tot(i);
        }
    int a[110]= {0};
    char str[11];
    for(int i=0; i<n; i++) {
        cin>>str;
        for(int j=m-1; j>=0; j--)
            if(str[j]=='H')
                a[i]|=(1<<i);
    }
    for(int i=1; i<=cnt; i++)
        dp[1][i][1]=t[i];
    for(int i=1; i<=cnt; i++)
        for(int j=1; j<=cnt; j++)
            dp[2][i][j]=max(dp[2][i][j],dp[1][j][1]+t[i]);
    for(int i=3; i<=100; i++)
        for(int j=1; j<=cnt; j++)
            if(!(s[j]&a[i]))
                for(int k=1; k<=cnt; k++)
                    if(!((s[k]&s[j])||(s[k]&a[i-1])))
                        for(int lk=1; lk<=cnt; lk++)
                            if(!((s[lk]&s[k])||(s[lk]&s[j])||(s[lk]&a[i-2])))
                                dp[i%3+1][j][k]=max(dp[i%3+1][j][k],dp[(i-1)%3+1][k][lk]+t[j]);
    int ans=0;
    for(int i=1; i<=cnt; i++)
        for(int j=1; j<=cnt; j++)
            ans=max(ans,dp[n%3+1][i][j]);
    cout<<ans;
    return 0;
}

by nuo0930 @ 2020-06-21 10:37:28

可是,还是错啊


by 一只书虫仔 @ 2020-06-21 10:42:53

% ClCN


上一页 |