动态规划

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; template <class T> inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF...

题目链接：点我~~ 题意：求两个串的最长公共递增子序列，并且子序列是连续的。 思路：令f(i)是以ai结尾的最大值, g(i)g是以bi结尾的最大值. 答案就是maxai=bj{min(f(i),g(j)}. dp一下就出来了. #include <bits/stdc++.h> using namespace std; typedef lon...

题目链接：点我~~ 题意：n 个pair<int , int>，每次可以选相邻两个pair。如果他们的first不互质就可以把它们都删掉，并且获得second之和的分数，问最大得分。 思路：设f[i][j]为[i,j]这段区间能取得的最大得分，转移就是不取左边/不取右边/断开拼起来/取两边，其中取两边需要中间能取干净才能取。复杂度 O(n^3)。...

题目链接：点我~~ 题意：一个数字，它每个数位上的奇数都形成偶数长度的段，偶数位都形成奇数长度的段他就是好的。问[L , R]的好数个数。 思路：裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的值的奇偶性和长度信息，还有是否前导零。 #include<bits/stdc++.h> using namespace std; ty...

简单dp~~ #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define mp make_pair #define lson l, ...

dp[i][j] 表示长度为i，重复的个数为j import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.BigInteger; impor...

通常的数位dp可以写成如下形式： int dfs(int i, int s, bool e) { if (i==-1) return s==target_s; if (!e && ~f[i][s]) return f[i][s]; int res = 0; int u = e?num[i]:9; for...

题目大意： 各位数字先增后减的数称为峰值数（位数大于等3且第一位非零），然后两个峰值数连在一起是一个bi-peak数，求两个数之间bi-peak数的各位数字之和的最大值。 解题思路： 数位dp，dp[i][j][k]表示当前后面还有i位，j表示前一位的数字，k表示与峰值的状态关系。 k=0 表示前面的为零，k=1表示前面恰好有一个在第一个波峰的上坡上，k=2...

题目大意：求指定范围内与7不沾边的所有数的平方和。通常的数位dp只是用来统计条件个数的，由于是求条件数的平方和，所以需要在过程中维护平方和。 解题思路：(以下内容来自互联网) 与7不沾边的数需要满足三个条件。 ①不出现7 ②各位数和不是7的倍数 ③这个数不是7的倍数 这三个条件都是基础的数位DP。 但是这题要统计的不是符合条件个数，而是平方和。 也就是说在D...

枚举每一位为中心的情况，进行判断就可以了。 #include<iostream> #include<cstdio> #include<string> #include<string.h> #include<algorithm> #include<cstdlib> #include<...