史上最玄学,求大佬解释一下

P2704 [NOI2001] 炮兵阵地

Lalenture @ 2018-08-26 13:18:01

# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
# include <map>
# define N 120
using namespace std;
int n,m;
char s[N][12];
int f[N];
int dp[N][1101][1101];
int can[1101];
int sum;
int MAX;

int get_sum(int x)  //统计情况中1的个数
{
    int ans=0;
    while(x)
    {
        if(x & 1) ans++;
        x >>= 1;
    }
    return ans;
}

void prepare()
{
    for(int i=0;i<MAX;i++)  //预处理比较麻烦,要仔细考虑所有情(我就忘了什么都不放的情况了)
            if((i&(i<<2))==0 && (i&(i<<1))==0)
            {
                can[++sum]=i;  //对于cann的处理可以加在单行处理中
                if((i&f[1])==0) dp[1][0][i]=get_sum(i);
                if((i&f[2])==0) dp[2][0][i]=get_sum(i);
            }

    for(int i = 1; i <= sum; i++)
        for(int j = 1; j <= sum; j++)
            if((can[i]&f[1])==0 && (can[j]&f[2])==0 && (can[i]&can[j])==0)
            {
                dp[2][can[i]][can[j]] = get_sum(can[i]) + get_sum(can[j]);
            }
}

int main()
{
    ios::sync_with_stdio(false);
    freopen("1.in","r",stdin);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        scanf("%s",s[i]+1);

    MAX = 1 << m;//全局变量在全局定义,不要再次在这里定义,即int MAX,又变成了局部变量 
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(s[i][j] == 'H')  f[i] = (f[i]<<1) + 1;
            else f[i] = f[i]<<1;
        }
    prepare();

    for(int i = 3; i <= n; i++)
        for(int j = 1; j <= sum; j++)
            if((f[i] & can[j]) == 0)
                for(int k = 1;k <= sum; k++)
                    if((f[i-1] & can[k]) == 0 && (can[j] & can[k]) == 0)
                        for(int l = 1; l <= sum; l++)
    if((f[i-2] & can[l]) == 0 && (can[j] & can[l]) == 0 && (can[k] & can[l]) == 0)
    {
        dp[i][can[k]][can[j]] = max(dp[i][can[k]][can[j]] , dp[i-1][can[l]][can[k]] + get_sum(can[j]));
    }

    int maxn = 0;
    for(int i = 1;i <= sum; i++)
        for(int j = 1; j <= sum; j++)
            maxn = max(maxn , dp[n][can[i]][can[j]]);

            cout<<maxn<<endl;
            return 0;
} 

这一组数据,用这个代码,直接复制粘贴,答案是6, 将数据储存在一个文件夹里,调用文件夹freopen("1.in","r",stdin)答案就变成7了

  • ,-

by Lalenture @ 2018-08-26 13:33:43

@ACの666 好的 , 谢谢大佬


by Lalenture @ 2018-08-26 14:42:26

@ACの666 我们老师解释了一下,他说用了ios::sync_with_stdio 优化,那么cin cout和scanf printf 不能混用。。


上一页 |