一个问题

P2704 [NOI2001] 炮兵阵地

Unknown__ @ 2023-08-03 17:29:01

如果不用特判,怎样过hack数据啊? 以下为100分wa代码

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int f[1 << 20],dp[110][1 << 10][1 << 10],n,m,A[101010],tot,pos[1 << 20];
signed main()
{
    cin>>n>>m;
    int i,j,k,l,o;
    for(i = 1;i <= n;i++)
        for(j = 0;j < m;j++)
        {
            char c;cin>>c;
            if(c == 'H')A[i] |= (1 << j);
        }
    for(i = 0;i < (1 << m);i++)
        if(!(i & (i << 1)) && !(i & (i << 2)))
        {
            f[++tot] = i;
            for(int t = i;t;t -= t & (-t))pos[tot]++;
        }
    for(i = 1;i <= tot;i++)
        if(!(A[1] & f[i]))
            dp[1][i][0] = pos[i];
    for(i = 1;i <= tot;i++)
        if(!(A[2] & f[i]))
            for(j = 1;j <= tot;j++)
                if(!(f[i] & f[j]))
                    dp[2][i][j] = pos[i] + pos[j];
    for(i = 3;i <= n;i++)
        for(j = 1;j <= tot;j++)
            if(!(A[i] & f[j]))
                for(k = 1;k <= tot;k++)
                    if(!(f[j] & f[k]) && !(f[k] & A[i - 1]))
                        for(l = 1;l <= tot;l++)
                            if(!(f[l] & f[k]) && !(f[l] & f[j]) && !(f[l] & A[i - 2]))
                                dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][l] + pos[j]);
    int ans = 0;
    for(i = 1;i <= tot;i++)
        for(j = 1;j <= tot;j++)
            ans = max(ans,dp[n][i][j]);
    cout<<ans;
}

by Unknown__ @ 2023-08-03 17:30:36

(还是说这就是一种极端情况,必须特判


by Austra @ 2023-08-08 10:31:56

不用特判,起码我没有


|