DAG上的dp 不要好高骛远去学这种高端东西，学了也写不对，剩下的几天把基本的dp和搜索搞下，就圆满了。不要再学新算法了，去九度把现有的算法写个痛。
学了数位DP和记忆搜索，今天遇到一道标准的水题，搞了三小时还没搞出来真是讽刺啊：
分析：
1.在任何时候，一个女生的左边或者右边至少有一个女生，这就是说若只有1个人，则这个人必须为男生。（竟然一直没意识到这点，我能说我要是看明白了这一行，就能ac吗？）
2.有n个人的排列，则应该从第n个人开始往第一个人推。这样思路就比较明确：不用去管第一个人究竟是男生还是女生，只用根据第n个人的性别，往前推。
第n个人可以是男生也可以是女生：总的排列数 = 第n个人是男生的情况 + 第n个人是女生的情况。
用dp[n][0]表示，有n个人的排列，排在第n个的是女生。用dp[n][1]表示，排在第n个的是女生
则： dp[n][0]应该加上dp[n-1][0]，因为若n-1个人的排列中第n-1个为女生，则外面还可以再坐一个女生。还应加上dp[n-2][1]，因为若第n-2个人为男生，则可以再坐2个女生。
#include <cstdio> const int MOD = 1000000007; const int MAXN = 1001; int dp[MAXN][2]; //dp[i][0] i个人，第一个为女生 //dp[i][1] i个人，第一个为男生 void init() { //只有1个人时，必须为男生 dp[1][0] = 0; dp[1][1] = 1; dp[2][0] = 1; dp[2][1] = 1; for (int i = 3; i < MAXN; ++i) { //若最前面为女生，则前面还可以坐一个女生, //最前面为男生，则可以做2个女生 dp[i][0] = (dp[i - 1][0] + dp[i - 2][1]) % MOD; dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int n; init(); while (scanf("%d", &n) != EOF) { printf("%d\n", (dp[n][0] + dp[n][1]) % MOD); } return 0; }
自己用记忆搜索搞的：
#include <cstdio> #include <memory.h> const int MOD = 1000000007; int dp[1001][2]; int dfs(int x, int t) { //第一个是男 || 女 if (x == 1 && t == 0) return 0; // <--------------1个人只可能是男 if (x == 1 && t == 1) return 1; if (x == 2) return 1; if (dp[x][t] != 0) return dp[x][t]; long long ret = 0; if (t == 0) { //前一个是女 ret += dfs(x - 1, 0); ret += dfs(x - 2, 1); // } else { ret += dfs(x - 1, 1); ret += dfs(x - 1, 0); } dp[x][t] = ret % MOD; return dp[x][t]; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int n; while (scanf("%d", &n) != EOF) { if (n == 1) { puts("1"); continue; } memset(dp, 0, sizeof dp); printf("%d\n", (dfs(n, 0) + dfs(n, 1)) % MOD); } return 0; }
实际上ret不必要用long long，2 * MOD < 2 ^ 31 - 1。
最长递增子序列：今天遇到2道这种题，都写错了。突然想起来这不是王道八套模拟上面的原题？当时是逐项相减变成最长连续子序列和的问题。现在竟然不会了。
传统的dp算法O(n^2)数据大于10000时会超时，故需要改进:不用动态规划的方法。
维护一个数组dp[n]，令dp[len]表示长度为len的子序列的最末尾的数字的最小值：（勉强想明白过程，还没想好该怎么表达）
1.由更新规则知：dp[i]严格递增，dp[2] > dp[1]必然成立。
2.对于每个新的数字k，必能找到一个长度为i的序列，使得其最后面的数字为k，这时就要更新dp[1...n]数组，使得dp[i] = k，那么
3.
#include <cstdio> const int MAXN = 100001; inline int Max(int a, int b) { return a > b ? a : b; } int len; int dp[MAXN]; //查找下界 int find(int x) { int left = 1; int right = len; while (left < right) { int mid = left + (right - left) / 2; if(dp[mid] >= x) right = mid; else left = mid+1; } return left; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int n; while (scanf("%d", &n) != EOF) { int num[MAXN]; for (int i = 1; i <= n; ++i) scanf("%d", &num[i]); len = 1; dp[len] = num[1]; for (int i = 2; i <= n; ++i) { if (num[i] > dp[len]) { dp[++len] = num[i]; } else {//更新 int pos = find(num[i]); dp[pos] = num[i]; } } printf("%d\n", len); } return 0; }
原文：http://www.cnblogs.com/fripside/p/3589489.html
