08
2017-08
2017-08
![UVALive 7648 Passwords (AC自动机 + DP)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
UVALive 7648 Passwords (AC自动机 + DP)
题意:~
思路:
#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...
08月08日
3,054
26
2016-09
2016-09
![HDU 5904 LCIS (DP)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 5904 LCIS (DP)
题目链接:点我~~
题意:求两个串的最长公共递增子序列,并且子序列是连续的。
思路:令f(i)是以ai结尾的最大值, g(i)g是以bi结尾的最大值. 答案就是maxai=bj{min(f(i),g(j)}. dp一下就出来了.
#include <bits/stdc++.h>
using namespace std;
typedef lon...
09月26日
1,911
18
2016-09
2016-09
![HDU 5900 QSC and Master (区间dp)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 5900 QSC and Master (区间dp)
题目链接:点我~~
题意:n 个pair<int , int>,每次可以选相邻两个pair。如果他们的first不互质就可以把它们都删掉,并且获得second之和的分数,问最大得分。
思路:设f[i][j]为[i,j]这段区间能取得的最大得分,转移就是不取左边/不取右边/断开拼起来/取两边,其中取两边需要中间能取干净才能取。复杂度 O(n^3)。...
09月18日
2,409
18
2016-09
2016-09
![HDU 5898 odd-even number (数位dp)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 5898 odd-even number (数位dp)
题目链接:点我~~
题意:一个数字,它每个数位上的奇数都形成偶数长度的段,偶数位都形成奇数长度的段他就是好的。问[L , R]的好数个数。
思路:裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的值的奇偶性和长度信息,还有是否前导零。
#include<bits/stdc++.h>
using namespace std;
ty...
09月18日
2,049
20
2016-07
2016-07
![Codeforces 698A Vacations (DP)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
Codeforces 698A Vacations (DP)
简单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, ...
07月20日
2,019
18
2016-03
2016-03
![Hdu 5642 King's Order (数位DP)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
Hdu 5642 King's Order (数位DP)
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...
03月18日
1,985
26
2016-02
2016-02
![[总结]数位统计模板](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
[总结]数位统计模板
通常的数位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...
02月26日
2,044
26
2016-02
2016-02
![HDU 3565 Bi-peak Number (数位dp)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 3565 Bi-peak Number (数位dp)
题目大意:
各位数字先增后减的数称为峰值数(位数大于等3且第一位非零),然后两个峰值数连在一起是一个bi-peak数,求两个数之间bi-peak数的各位数字之和的最大值。
解题思路:
数位dp,dp[i][j][k]表示当前后面还有i位,j表示前一位的数字,k表示与峰值的状态关系。
k=0 表示前面的为零,k=1表示前面恰好有一个在第一个波峰的上坡上,k=2...
02月26日
2,137
26
2016-02
2016-02
![HDU 4507 恨7不成妻 (数位DP)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 4507 恨7不成妻 (数位DP)
题目大意:求指定范围内与7不沾边的所有数的平方和。通常的数位dp只是用来统计条件个数的,由于是求条件数的平方和,所以需要在过程中维护平方和。
解题思路:(以下内容来自互联网)
与7不沾边的数需要满足三个条件。
①不出现7
②各位数和不是7的倍数
③这个数不是7的倍数
这三个条件都是基础的数位DP。
但是这题要统计的不是符合条件个数,而是平方和。
也就是说在D...
02月26日
2,188
25
2016-02
2016-02
![HDU 3709 Balanced Number (数位DP)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 3709 Balanced Number (数位DP)
枚举每一位为中心的情况,进行判断就可以了。
#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<...
02月25日
2,184