首页 > 其他分享 >#轮廓线dp#HDU 1400 Mondriaan's Dream

#轮廓线dp#HDU 1400 Mondriaan's Dream

时间:2023-08-04 16:45:36浏览次数:47  
标签:HDU int Mondriaan two long 轮廓线 1400 dp

题目传送门


分析

状压dp会TLE,考虑用轮廓线dp,

设 \(dp[i][j][S]\) 表示现在处理到 \((i,j)\) 这个位置轮廓线上状态为 \(S\) 的情况

二进制位为1表示左边或者上方有骨牌跨过轮廓线,然后分类讨论转移一下即可


代码

#include <cstdio>
#include <cstring> 
using namespace std;
const int two[11]={1,2,4,8,16,32,64,128,256,512,1024};
int n,m,al; long long f[2053],dp[2053];
int main(){
    while (scanf("%d%d",&n,&m)==2&&n){
        if (n<m) n^=m,m^=n,n^=m;
        f[0]=1,al=1<<m;
        for (int i=1;i<(1<<m);++i) f[i]=0;
        memcpy(dp,f,sizeof(long long)*al);
        for (int i=0;i<n;++i)
        for (int j=0;j<m;++j){
            memset(f,0,sizeof(long long)*al);
            for (int k=0;k<al;++k)
            if ((k>>j)&1) f[k^two[j]]+=dp[k];//上一行已竖放
            else{
                if (j<m-1&&!((k>>(j+1))&1)) f[k^two[j+1]]+=dp[k];//横放
                f[k^two[j]]+=dp[k];//竖放
            }
            memcpy(dp,f,sizeof(long long)*al); 
        }
        printf("%lld\n",dp[0]);
    }
    return 0;
} 

标签:HDU,int,Mondriaan,two,long,轮廓线,1400,dp
From: https://www.cnblogs.com/Spare-No-Effort/p/17606373.html

相关文章

  • 耗时四年,我们写了一本1400页的AI全栈技术手册
    不知不觉写文章已经四年了。最开始是一个人,后来恰了恰饭,就招揽了很多比小夕厉害的小伙伴一起写。不知不觉已经积累了300多篇了。。三年以来,我跟小伙伴们原创的300+篇深度学习、NLP、CV、知识图谱、跨模态等领域的入门资料、子方向综述、2018~2022学术前沿解读、工业界炼丹经验与算......
  • HDU7331 另解
    \[\begin{aligned}ANS&=\sum_{i=1}^n\binom{n}{i}p^i(1-p)^{n-i}\left(\sum_{j=1}^ij^m\right)&p=\frac{a}{b}\\&=\sum_{j=1}^nj^m\sum_{i=j}^n\binom{n}{i}p^i(1-p)^{n-i}\\&=\sum_{j=1}^n\sum_{k=0}^m{m\bracek}\binom{j}{k}k!\su......
  • HDU1151—Air Raid(最小路径覆盖)
    【\(HDU1151\)】—\(Air\)\(Raid\)(最小路径覆盖)题解描述给定一个\(DAG\)(有向无环图),选定最少的点,使得从这些点出发可以覆盖每一条路径(即每个点都经过至少一遍)。输入:24334132333131223输出21以测试数据为例,\(4\)个路口,\(3\)条路。现派伞兵经过所有......
  • hdu7319 String and GCD
    StringandGCD首先我们需要用kmp的fail建树,然后需要利用到欧拉反演。\[n=\sum_{d|n}\varphi(d)\]对于这题来说\[(i,j)=\sum_{d|(i,j)}\varphi(d)=\sum_{d|i,d|j}\varphi(d)\]那么我们只需要用一个桶存每个约数从根到当前节点出现了多少次。然后枚举约数也有一个技巧,具体......
  • HDU 1312 Red and Black 题解
    //注意边界判断,调了好久#include<iostream>#include<queue>usingnamespacestd;#definecheck(x,y)(x<wx&&x>=0&&y<hy&&y>=0)structnode{intx,y;};charroom[23][23];intn,m,wx,hy,num;intdir[4][2]={......
  • HDU 暑假多校 2023 第四场
    目录写在前面731773237314732173227318写在最后写在前面补题地址:https://acm.hdu.edu.cn/listproblem.php?vol=64,题号7312~7323。我是飞舞。小子们哪,你们要自守,远避偶像。Dearchildren,keepyourselvesfromidols.——约翰一书以下按照个人向难度排序。7317签到,特......
  • HDU1702 ACboy needs your help again! 题解
    #include<iostream>#include<string>#include<queue>#include<stack>usingnamespacestd;intt,n,m;intmain(){cin>>t;while(t--){queue<int>q;stack<int>s;stringop,str......
  • HDU4841 AHOI1999 圆桌问题 题解
    朴素的约瑟夫问题,用vector处理即可#include<iostream>#include<vector>usingnamespacestd;//AHOI1999圆桌问题类似于约瑟夫问题vector<int>table;intn,m;intmain(){while(cin>>n>>m){table.clear();for(inti=0;......
  • HDU−4825 XorSum
    01trie树定义:将整数转化为二进制再插入trie树,通常是从高位到低位插入trie。使用场景:寻找与异或相关的结果题目背景:Zeus和Prometheus做了一个游戏,Prometheus给Zeus一个集合,集合中包含了N个正整数,随后Prometheus将向Zeus发起M次询问,每次询问中包含一个正整数S,之后......
  • HDU 暑假多校 2023 第三场
    目录写在前面731073047311写在最后写在前面补题地址:https://acm.hdu.edu.cn/listproblem.php?vol=64,题号7300~7311。坐牢场。老东西怎么还在圈里混啊(恼以下按个人向难度排序,标题为题库中题号。7310模拟这个过程。缩放至\(Z\%\)即将原来的某个像素覆盖的范围\((x-1,y-1......