当前位置: 首页 > news >正文

状压DP

状压DP

题意:\(n * n\) 的棋盘里面放 \(k\) 个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 15, M = 150, K = 1500;
LL n, k;
LL cnt[K];    //每个状态的二进制中 1 的数量
LL tot;    //合法状态的数量
LL st[K];    //合法的状态
LL dp[N][M][K];    //第 i 行,放置了 j 个国王,状态为 k 的方案数
int main(){ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;for (int s = 0; s < (1 << n); s ++ ){  //找出合法状态LL sum = 0, t = s;while(t){  //计算 1 的数量sum += (t & 1);t >>= 1;}cnt[s] = sum;if ( (( (s << 1) | (s >> 1) ) & s) == 0 ){  //判断合法性st[ ++ tot] = s;}}dp[0][0][0] = 1;for (int i = 1; i <= n + 1; i ++ ){for (int j1 = 1; j1 <= tot; j1 ++ ){    //当前的状态LL s1 = st[j1];for (int j2 = 1; j2 <= tot; j2 ++ ){    //上一行的状态LL s2 = st[j2];if ( ( (s2 | (s2 << 1) | (s2 >> 1)) & s1 ) == 0 ){for (int j = 0; j <= k; j ++ ){if (j - cnt[s1] >= 0)dp[i][j][s1] += dp[i - 1][j - cnt[s1]][s2];}}}}}cout << dp[n + 1][k][0] << "\n";return 0;
}

常用例题

题意:在一篇文章(包含大小写英文字母、数字、和空白字符(制表/空格/回车))中寻找 \({\tt helloworld}\)(任意一个字母的大小写都行)的子序列出现了多少次,输出结果对 \(10^9+7\) 的余数。

字符串 DP ,构建一个二维 DP 数组,\(dp[i][j]\)\(i\) 表示文章中的第几个字符,\(j\) 表示寻找的字符串的第几个字符,当字符串中的字符和文章中的字符相同时,即找到符合条件的字符, dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] ,因为字符串中的每个字符不会对后面的结果产生影响,所以 DP 方程可以优化成一维的, 由于字符串中有重复的字符,所以比较时应该从后往前。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e9 + 7;
char c, s[20] = "!helloworld";
LL dp[20];
int main(){dp[0] = 1;while ((c = getchar()) != EOF)for (int i = 10; i >= 1; i--)if (c == s[i] || c == s[i] - 32)dp[i] = (dp[i] + dp[i - 1]) % mod;cout << dp[10] << "\n";return 0;
}

题意:(最长括号匹配)给一个只包含‘(’,‘)’,‘[’,‘]’的非空字符串,“()”和“[]”是匹配的,寻找字符串中最长的括号匹配的子串,若有两串长度相同,输出靠前的一串。

设给定的字符串为 \(\tt{}s\) ,可以定义数组 \(dp[i], dp[i]\) 表示以 \(s[i]\) 结尾的字符串里最长的括号匹配的字符。显然,从 \(i - dp[i] + 1\)\(i\) 的字符串是括号匹配的,当找到一个字符是‘)’或‘]’时,再去判断第 \(i - 1 - dp[i - 1]\) 的字符和第 \(i\) 位的字符是否匹配,如果是,那么 dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
string s;
int len, dp[maxn], ans, id;
int main(){cin >> s;len = s.length();for (int i = 1; i < len; i++){if ((s[i] == ')' && s[i - 1 - dp[i - 1]] == '(' ) || (s[i] == ']' && s[i - 1 - dp[i - 1]] == '[')){dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]];if (dp[i] > ans) {ans = dp[i];  //记录长度id = i;  //记录位置}}}for (int i = id - ans + 1; i <= id; i++)cout << s[i];cout << "\n";return 0;
}

题意:去掉区间内包含“4”和“62”的数字,输出剩余的数字个数

int T,n,m,len,a[20];//a数组用于判断每一位能取到的最大值
ll l,r,dp[20][15];
ll dfs(int pos,int pre,int limit){//记搜//pos搜到的位置,pre前一位数//limit判断是否有最高位限制if(pos>len) return 1;//剪枝if(dp[pos][pre]!=-1 && !limit) return dp[pos][pre];//记录当前值ll ret=0;//暂时记录当前方案数int res=limit?a[len-pos+1]:9;//res当前位能取到的最大值for(int i=0;i<=res;i++)if(!(i==4 || (pre==6 && i==2)))ret+=dfs(pos+1,i,i==res&&limit);if(!limit) dp[pos][pre]=ret;//当前状态方案数记录return ret;
}
ll part(ll x){//把数按位拆分len=0;while(x) a[++len]=x%10,x/=10;memset(dp,-1,sizeof dp);//初始化-1(因为有可能某些情况下的方案数是0)return dfs(1,0,1);//进入记搜
}
int main(){cin>>n;while(n--){cin>>l>>r;if(l==0 && r==0)break;if(l) printf("%lld\n",part(r)-part(l-1));//[l,r](l!=0)else printf("%lld\n",part(r)-part(l));//从0开始要特判}
}
http://www.hskmm.com/?act=detail&tid=37727

相关文章:

  • 搞定三大PLC通讯:倍福与西门子、欧姆龙与西门子数据互通实战
  • 实验p66
  • 牛客2025秋季算法编程训练联赛2-(基础组提升组)
  • 局域网共享一键通_v2.0.9.9
  • newDay15
  • 每日反思(2025_10_23)
  • 树链剖分/轻重链剖分
  • 如何降低信息化系统的构建成本? ——信息化系统省钱全攻略:从规划到运维的实用技巧
  • C#编程时winform程序登陆记住密码和自动登录功能,关于App.config的问题及解决方案
  • 2025.10.23总结
  • Day2超链接标签
  • Ai元人文构想:你喜欢黑箱与偏见
  • 企业微信 使用api批量处理群消息
  • first game (1)
  • 10月23日日记
  • Gin笔记一之项目建立与运行
  • 软件工程学习日志2025.10.23
  • 10月23号
  • 【题解】P14254 分割(divide)
  • 数论分块 - R
  • 第九届强网杯线上赛PWN_flag-market
  • ISFB银行木马家族演化史:从Gozi到LDR4的技术剖析
  • 10.23日学习笔记
  • 埃氏筛及扩展质因数筛——埃拉托斯特尼筛法变种
  • exgcd板子
  • 2025.10.23
  • 编程练习
  • Codeforces Round 976 (Div. 2) A. Find Minimum Operations
  • 手机号md5解密/身份证号码md5解密/手机号运营商+归属地查询
  • 102302142罗伟钊第一次作业