Loading...

SCOI2005 互不侵犯

check评论:0 条 remove_red_eye浏览量:277 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-13

一道简单的状态压缩dp
网上都是题解qwq
我这就发代码就好啦qwq

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt,MAX;
long long dp[20][1000][400];
int can[1000],num[2000];
int getsum(int x)
{
    int ret=0;
    while(x) 
    {
        ret+=(x&1); 
        x>>=1;
    }
    return num[cnt]=ret;
}
int main()
{
    long long ans=0;
    scanf("%d%d",&n,&m);
    MAX=(1<<n)-1;
    for(int i=0;i<=MAX;i++) 
    {
        if(!(i&(i<<1))) 
        {
            can[++cnt]=i;
            dp[1][cnt][getsum(i)]=1;
        }
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            int x=can[j];
            for(int k=1;k<=cnt;k++)
            {
                int y=can[k];
                if((x&y)||(x&(y<<1))||(x&(y>>1))) 
                {
                    continue;
                }
                for(int l=0;l<=m;l++) 
                {
                    dp[i][j][num[j]+l]+=dp[i-1][k][l];
                }
            }
        }
    }
    for(int i=1;i<=cnt;i++) 
    {
        ans+=dp[n][i][m];
    }
    printf("%lld",ans);
}

chevron_left NOIP2017 宝藏
树的dfs序 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名