题目描述

咳咳,懒得复制了上面是两张图:)

解题思路

这题是一道很好的题,感觉之前做过,一开始手推状态找规律,可以用状压但是没想到

借鉴了一下大佬的dp

modify数组用以累加新增的状态数

dp数组表示前i列第j个连通块,a,b表示该列的状态,转移方程见代码

下面就是美丽的代码了

AC Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define P (LL)(998244353) typedef long long LL;
typedef long double ld;
typedef unsigned long long ULL; using namespace std; const int MAXN = + ;
const int MAXK = MAXN << ;
int dp[MAXN][MAXK][][];
int modify[][][][];
void pre() {
modify[][][][] = ; modify[][][][] = ; modify[][][][] = ; modify[][][][] = ;
modify[][][][] = ; modify[][][][] = ; modify[][][][] = ; modify[][][][] = ;
modify[][][][] = ; modify[][][][] = ; modify[][][][] = ; modify[][][][] = ;
modify[][][][] = ; modify[][][][] = ; modify[][][][] = ; modify[][][][] = ;
}
int main() {
int n , k;
cin>>n>>k;
pre();
dp[][][][] = dp[][][][] = ;
dp[][][][] = dp[][][][] = ; for(int i = ; i <= n; i++)
for(int j = ; j <= k; j++)
for(int a = ; a < ; a++)
for(int b = ; b < ; b++)
for(int A = ; A < ; A++)
for(int B = ; B < ; B++) {
int block = modify[A][B][a][b];
if(j >= block) dp[i][j][a][b] = (dp[i][j][a][b] + dp[i - ][j - block][A][B]) % P;
}
int ans = ;
for(int A = ; A < ; A++)
for(int B = ; B < ; B++)
ans = (ans + dp[n][k][A][B]) % P;
cout<<ans;
return ;
}

最新文章

  1. C语言学习017:malloc和free
  2. Linux Strip
  3. iwpriv
  4. [hackerrank]Palindrome Index
  5. IOS调用相机相册
  6. WEB网站常见受攻击方式及解决办法
  7. c#中[Flags] 枚举类型定义问题_百度知道
  8. Android Studio 模拟器 不要皮肤,效果更好
  9. Codeforces 435B. Pasha Maximizes
  10. 【BZOJ3627】【JLOI2014】路径规划 分层图
  11. android视频播放器系列(一)——系统播放器
  12. [Usaco2005 dec]Layout 排队布局 差分约束
  13. 软件定义网络(Software Defined Network,SDN)简介
  14. LR socket协议脚本
  15. 并查集(POJ1182)
  16. java多线程快速入门(十七)
  17. 给你的网站添加 console.js
  18. python urlopen
  19. VisualSVN:强制必须填写日志信息
  20. zabbix3.2的server和zabbix-agent2.2怎么监控MySQL的办法

热门文章

  1. Call to undefined function imagecreatefromjpeg() 让GD支持JPEG格式的图片扩展
  2. 【JZOJ6222】【20190617】可爱
  3. 【洛谷P5049】旅行(数据加强版)
  4. 前端微信小程序云开发基础讲解
  5. (7)Go切片
  6. 刷题记录:[BUUCTF 2018]Online Tool
  7. RocketMQ官方启动脚本不支持jdk11的修改
  8. ubantu使用ssh服务
  9. Angularjs 标签使用整理
  10. Android原生同步登录状态到H5网页避免二次登录