—— “Hala, AbandonZHANG！”~ ------------------------------------------------------------- ◊
线性DP： 经典DP原型系列： ° （
最长下降子序列入门）
思路：比较简单，第一问最长不上升子序列；第二问贪心即可（有人证明第二问等价于求最长上升子序列。。。）。
状态转移方程：最长不上升子序列：s[i] = max(s[i], s[j]+1) (j = 0...i-1, 且a[j] >= a[i])
#include #include #include using namespace std;int a[1010];int n;int work1(int n){ int s[1010]; int res = 0; for (int i = 0; i < 1010; i ++) s[i] = 1; for (int i = 0; i < n; i ++) { for (int j = 0; j < i; j ++) if (a[i] <= a[j]) s[i] = max(s[i],s[j] + 1); if (s[i] > res) res = s[i]; } return res;}int work2(int n){ int res = 0; int vis[1010] = {0}; for (int i = 0; i < n; i ++) if (!vis[i]) { res ++; vis[i] = 1; int tmp = a[i]; for (int j = i + 1; j < n; j ++) if (a[j] <= tmp && vis[j] == 0) { vis[j] = 1; tmp = a[j]; } } return res;}int main(){ scanf("%d",&n); for (int i = 0; i < n; i ++) scanf("%d",&a[i]); printf("%d%d\n",work1(n),work2(n)); return 0;} ° （
最长下降子序列）
思路：分别把每个点看成中间最高的人，两边的人数就是求一下从左端到该点的最长上升子序列、从右端到该点的最长下降子序列加起来。然后判断那个点做中间点时需要去除的人数最少就行了。
#include #include using namespace std;int a[105],s[105],w[105];void works(int n){ for (int i = 0; i < n; i ++) s[i] = w[i] = 1; for (int i = 0; i < n; i ++) for (int j = 0; j < i; j ++) if (a[j] < a[i]) s[i] = max(s[i], s[j] + 1); for (int i = n - 1; i >= 0; i --) for (int j = n - 1; j > i; j --) if (a[j] < a[i]) w[i] = max(w[i], w[j] + 1);}int cnt(int n){ int res = 200; works(n); for (int i = 0; i < n; i ++) if (n - (s[i] + w[i] - 1) < res) res = n - (s[i] + w[i] - 1); return res;}int main(){ int n; scanf("%d",&n); for (int i = 0; i < n; i ++) scanf("%d",&a[i]); printf("%d\n",cnt(n)); return 0;} º ★（
石子合并原形，
区间划分DP）
思路：典型的区间划分DP。f[i,j]表示区间[i..j]的石堆合并成一个的得分。因为题目中说，只能归并相邻的两堆石子。所以，f[i,j]这一系列石子必然由f[i,k]和f[k+1,j]（i<=k<j）这两堆石子归并而来。只要在所有的f[i,k]+f[k+1,j]中取个最小值（就是原来此次没归并前的最小值），加上自己本身所有石子的和（因为归并一次的代价是所有石子的总和），就是我们要求的f[i,j]。 其次是要注意
圆形问题转线形的方法：
将石子序列倍长，答案在s[i][i + n - 1] (i = 0 .. n - 1)中找。
#include #include using namespace std;int n;int a[205],s[205][205],t[205][205];int num[205][205];int calnum(){ for (int i = 0; i < 2 * n - 1 ; i ++) num[i][i] = a[i]; for (int p = 1; p < n; p ++) for (int i = 0; i < 2 * n - 1; i ++) { if (i + p < 2 * n - 1) { int j = i + p; num[i][j] = num[i][i] + num[i + 1][j]; } }}int calmin(){ for (int i = 0; i < 205; i ++) for (int j = 0; j < 205; j ++) s[i][j] = 1e8; for (int i = 0; i < 2 * n - 1 ; i ++) s[i][i] = 0; for (int k = 1; k < n; k ++) for (int i = 0; i < 2 * n - 1; i ++) { if (i + k < 2 * n - 1) { int j = i + k; for (int p = i; p < j; p ++) s[i][j] = min(s[i][j], s[i][p] + s[p + 1][j] + num[i][p] + num[p + 1][j]); } } int res = 1e8; for (int i = 0; i < n; i ++) if (s[i][i + n - 1] < res) res = s[i][i + n - 1]; return res;}int calmax(){ for (int p = 1; p < n; p ++) for (int i = 0; i < 2 * n - 1; i ++) { if (i + p < 2 * n - 1) { int j = i + p; for (int k = i; k < j; k ++) t[i][j] = max(t[i][j], t[i][k] + t[k + 1][j] + num[i][k] + num[k + 1][j]); } } int res = 0; for (int i = 0; i < n; i ++) if (t[i][i + n - 1] > res) res = t[i][i + n - 1]; return res;}int main(){ scanf("%d",&n); for (int i = 0; i < n; i ++) { scanf("%d",&a[i]); a[i + n] = a[i]; } calnum(); printf("%d\n%d\n",calmin(),calmax()); return 0;} º （
石子合并）
思路：之前做过一次，有点儿压力。。。然后去做石子合并。会了石子合并了这题就出来了，1Y。思路一样的。只不过这里一个石子有左右值。好久没1Y了，好高兴^ ^~
#include #include using namespace std;int n;int l[210][210],r[210][210],s[210][210];int ff(){ for (int p = 1; p < n; p ++) for (int i = 0; i < 2 * n - 1; i ++) if (i + p < 2 * n - 1) { int j = i + p; for (int k = i; k < j; k ++) { s[i][j] = max(s[i][j], s[i][k] + s[k+1][j] + l[i][k] * r[i][k] * r[k+1][j]); l[i][j] = l[i][k]; r[i][j] = r[k+1][j]; } } int res = 0; for (int i = 0; i < n; i ++) if (s[i][i + n - 1] > res) res = s[i][i + n - 1]; return res;}int main(){ scanf("%d",&n); for (int i = 0; i < n; i ++) { int q; scanf("%d",&q); l[i][i] = q; if (i != 0) r[i-1][i-1] = q; if (i == n - 1) r[i][i] = l[0][0]; } for (int i = 0; i < n; i ++) { l[i+n][i+n] = l[i][i]; r[i+n][i+n] = r[i][i]; } printf("%d\n",ff()); return 0;} º （
石子合并）
思路：这题我是按石子合并的区间DP思路做的，f[i][j][kk]表示区间[i..j]的数被kk个乘号划分成k+1个数的乘积。然后f[i][j][kk] = max{num[i][w] * f[w+1][j][kk-1]}。但是我们可以发现这个状态转移方程中j一直没变对不对？所以我们其实可以降低一维：令f[i][k]表示把前i个数用k个乘号划分成k+1个数的乘积，则f[i][k] = max{num[i][w] * f[w+1][k-1]}。 PS:这题那年普及组和提高组都有，不过普及组k<=6，数据范围int；提高组k<=30，数据范围long long。RQNOJ上是提高组的。
#include #include #include using namespace std;int n,k;int a[50];int f[50][50][40];int num[50][50];void calnum(){ for (int p = 1; p < n; p ++) for (int i = 0; i < n; i ++) if (i + p < n) { int j = i + p; if (j - 1 == i) num[i][j] = a[i] * 10 + a[j]; num[i][j] = num[i][j-1] * 10 + a[j]; }}int ff(){ calnum(); for (int p = 1; p < n; p ++) for (int i = 0; i < n; i ++) if (i + p < n) { int j = i + p; for (int w = i; w < j; w ++) for (int kk = 1; kk <= k; k ++) f[i][j][kk] = max(f[i][j][kk], num[i][w] * f[w+1][j][kk-1]); } return f[0][n-1][k];}int main(){ scanf("%d %d",&n,&k); char s[50]; gets(s); for (int i = 0; i < n; i ++) a[i] = s[i] - '0'; printf("%d\n",ff()); return 0;} º （
石子合并）
思路：变相的乘积最大呐。。。就是区间num计算的方法换一下而已嘛。。。设f[i][j]为从第i个开始一直到尾划分成j+1段的单词数。 但是还是暴露除了几个值得关注的问题：
区间划分DP中一定要注意判断当前区间可不可以划分，即判断[i..j]区间的大小是否大于划分数k。这个问题其实在上一道乘积最大的题目中也暴露出来了，只不过因为那里是乘的关系所以f[][]为0不会影响结果，但加可就得严格限制了。。。比如如果是aaaaaaaaaaaaaaaaaaaa要划分成4段，有一个子串aaaaa。标准答案是13，即分成[0..16][17][18][19]。不加那个if (snum - w - 1 > c - 1)判断算出来是15，他的15是由f[0][k] = num[0][18] + f[19][k - 1]得出的，但我们发现[19]根本不能划分成k段对不？ 题目中还说“ 每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th ”，这个其实很好限制，我们在计算某个区间内有多少个子串时暴力枚举，当我们对区间[i,j]的串的第一个开头配对某个子串成功后直接跳出不管后面的子串而去配对下一个开头就可以了。。。（说的不是很清楚，还是看代码领悟吧。。。）
#include #include #include using namespace std;int p,k,o;int snum;char a[205];char q[7][205];int num[205][205];int f[205][50];void calnum(){ for (int i = 0; i < snum; i ++) for (int j = i; j < snum; j ++) { for (int m = i; m <= j; m ++) for (int w = 0; w < o; w ++) { int l; for (l = 0; l < strlen(q[w]); l ++) if (m + l > j || q[w][l] != a[m + l]) break; if (l == strlen(q[w])) { num[i][j] ++; break; } } }// for (int i = 0; i < snum; i ++)// for (int j = i; j < snum; j ++)// printf("i = %d, j = %d, num = %d\n",i,j,num[i][j]);}int ff(){ calnum(); for (int i = 0; i < snum; i ++) f[i][0] = num[i][snum - 1]; for (int c = 1; c <= k; c ++) for (int i = snum - 1; i >= 0; i --) for (int w = i; w < snum - 1; w ++) if (snum - w - 1 > c - 1) f[i][c] = max(f[i][c], num[i][w] + f[w+1][c-1]); return f[0][k];}int main(){ char s[25]; scanf("%d%d",&p,&k); k --; while(p --) { scanf("%s",s); for (int i = 0; i < 20; i ++) a[snum ++] = s[i]; } scanf("%d",&o); for (int i = 0; i < o; i ++) scanf("%s",q[i]); printf("%d\n",ff()); return 0;} ° ★（
方格取数原形，
多线程DP） 一取方格数：f[i][j] = max(f[i-1][j], f[i][j-1])。二取方格数当然也有类似的O(n^4)的思路。 但有一个更好的
思路：
可以发现在走到第n步时，能走到的格子是固定的。进一步发现，这些格子的横纵坐标加起来都是n+1（左上角（1，1））。这样我们就不必同时记录两个坐标了，只要知道其中一个t，另一个就可以通过n+1-t算出来。这个方法在一取方格（只走一条路）时效果并不明显，这里可以看到已经减少了一维，且越是高维优点越明显。 用f[x,i,j]表示走到第x步时，第1条路线走到横坐标为i的地方，第2条路线走到了横坐标为j的地方。这样，我们只要枚举x，i，j，就能递推出来了。
#include #include using namespace std;int n;int f[31][11][11];int a[11][11];int main(){ scanf("%d",&n); int x,y,c; while(scanf("%d%d%d",&x,&y,&c)) { if (x == 0 && y == 0 && c == 0) break; a[x][y] = c; } for (int k = 1; k <= n + n; k ++) for (int i = 1; i <= min(n,k); i ++) for (int j = 1; j <= min(n,k); j ++) { f[k][i][j] = max(f[k-1][i][j], f[k-1][i-1][j]); f[k][i][j] = max(f[k][i][j], f[k-1][i][j-1]); f[k][i][j] = max(f[k][i][j], f[k-1][i-1][j-1]); if (i == j) f[k][i][j] += a[i][k+1-i]; else f[k][i][j] += a[i][k+1-i] + a[j][k+1-j]; } printf("%d\n",f[n+n][n][n]); return 0;} vijos上还有三取方格数（ ）。
N取方格数这种问题可以用费用流建模做。 ------------------------------------------------------------------------------- º （
方格取数）
思路：方格取数啊~只不过限制每个格子只能走一次，所以当两个坐标一样时直接f[][][] = 0就行了~（当然最后一步需要特殊处理一下）
#include #include using namespace std;int m,n;int f[110][55][55];int a[55][55];int main(){ scanf("%d%d",&m,&n); for (int i = 1; i <= m; i ++) for (int j = 1; j <= n; j ++) scanf("%d",&a[i][j]); for (int k = 1; k < m + n; k ++) for (int i = 1; i <= min(m,k); i ++) for (int j = 1; j <= min(m,k); j ++) { f[k][i][j] = max(f[k-1][i][j], f[k-1][i-1][j]); f[k][i][j] = max(f[k][i][j], f[k-1][i][j-1]); f[k][i][j] = max(f[k][i][j], f[k-1][i-1][j-1]); if (i == j) if (i == m) f[k][i][j] += a[i][k+1-i]; else f[k][i][j] = 0; else f[k][i][j] += a[i][k+1-i] + a[j][k+1-j]; } printf("%d\n",f[m+n-1][m][m]); return 0;} º （
路径压缩）
思路：DP+路径压缩。可以证明当两石块之间的距离大于它的时候，那么大于它的部分的每一个点都可以通过这两个数的某一种组合跳到，所以当两个石块间的距离大于这个最小公倍数，那么就把它们的距离缩小到这个最小公倍数.路径压缩后，就可以DP求出最小踩石子个数。设f[i]表示到达第i个位置最小踩多少个石子.则f[i]=min(f[i-j]+d[i])（1<=i<=l+t)(s<=j<=t),d[i]表示第i个位置是否有石子.最后的答案就是在l to l+t 之间找最小。
#include #include #include #include using namespace std;int a[105],f[20000],d[20000];int main(){ int l, m, s, t; memset(f,0,sizeof(f)); memset(d,0,sizeof(d)); cin >> l; cin >> s >> t >> m; for (int i = 1; i <= m; i ++){ cin >> a[i]; } int res = 0; if (s == t){ for (int i = 1; i <= m; i ++){ if (a[i] % s == 0){ res ++; } } cout< 90){ a[i+1] = a[i] + (a[i+1] - a[i]) % 90; } } l = a[m+1]; for (int i = 1; i <= m; i ++){ d[a[i]] = 1; } for (int i = 1; i <= l + t; i ++){ f[i] = 0xFFFFFFF; } for (int i = 1; i <= l + t; i ++){ for (int j = s; j <= t; j ++){ if (i >= j){ f[i] = min(f[i], f[i-j] + d[i]); } } } int minn = 0xFFFFFFF; for (int i = l; i <= l + t; i ++){ if (f[i] < minn){ minn = f[i]; } } cout #include #include #include using namespace std;const int N = 50010;int dp1[N],dp2[N],b1[N],b2[N],a[N];void go_dp(int n){ //left b1[0] = a[0]; dp1[0] = b1[0]; int max = dp1[0]; for (int i = 1; i < n; i ++){ if (b1[i-1] > 0){ b1[i] = b1[i-1] + a[i]; } else{ b1[i] = a[i]; } if (b1[i] > max){ max = b1[i]; } dp1[i] = max; } //right b2[n-1] = a[n-1]; dp2[n-1] = b2[n-1]; max = dp2[n-1]; for (int i = n - 2; i >= 0; i --){ if (b2[i+1] > 0){ b2[i] = b2[i+1] + a[i]; } else{ b2[i] = a[i]; } if (b2[i] > max){ max = b2[i]; } dp2[i] = max; }}int ff(int n){ int max = INT_MIN; for (int i = 0; i < n - 1; i ++){ if (dp1[i] + dp2[i+1] > max){ max = dp1[i] + dp2[i+1]; } } return max;}int main(){ int t,n; scanf("%d",&t); while(t --){ scanf("%d",&n); for (int i = 0; i < n; i ++){ scanf("%d",&a[i]); } go_dp(n); printf("%d\n",ff(n)); } //system("pause"); return 0;} º ★(
最大子矩阵和)
题目大意：最大子矩阵和。
思路：如果不是方阵而是一维数组，显然是最大连续子段和。如果已经确定这个矩形应该包含哪些行，而还不知道该包含哪些列，那么可以将每一列的各行元素相加，从而将矩阵转换为一维数组的最大连续子段和。因此，只要我们枚举矩阵应该从哪一行到哪一行，就可以将问题用最大连续子段和策略来求解了，O(N
3)。
#include #include #include #include using namespace std;int a[120][120];int b[120],dp[120];int main(){ int maxn; int n; while(scanf("%d",&n) == 1){ maxn = INT_MIN; for (int i = 0; i < n; i ++){ for (int j = 0; j < n; j ++){ scanf("%d",&a[i][j]); maxn = max(maxn, a[i][j]); } } for (int i = 0; i < n; i ++){ memset(b,0,sizeof(b)); for (int j = i; j < n; j ++){ dp[0] = 0; for (int k = 0; k < n; k ++){ b[k] += a[j][k]; dp[k+1] = (dp[k] > 0 ? dp[k] : 0) + b[k]; maxn = max(maxn, dp[k+1]); } } } printf("%d\n",maxn); } return 0;} º (
字符串编辑距离(Levenshtein distance))
题目大意：给定字符串A和B。求A串转到B串所需的最少编辑操作次数。编辑操作包括：删除、添加一个字符、替换成任意字符。
思路：dp[i][j]，代表字符串1的前i子串和字符串2的前j子串的距离。初始化dp[0][0] = 0,dp[i][0] = i,dp[0][j] = j; dp[i][j] = min { dp[i][j-1] + 1 //添加(在i位置后面添加一个字符) dp[i-1][j] + 1 //删除(删除第i个字符) dp[i-1][j-1] + (A[i] == B[i]?0:1) //替换 }
#include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)using namespace std;typedef long long LL; //max long long == 9223372036854775807LLint f[1010][1010];char s1[1010],s2[1010];int main(){ int l1,l2; while(cin>>l1){ cin>>s1; cin>>l2; cin>>s2; for (int i = 0; i < 1010; i ++){ for (int j = 0; j < 1010; j ++){ f[i][j] = INT_MAX; } } for (int i = 0; i <= l1; i ++){ f[i][0] = i; } for (int i = 0; i <= l2; i ++){ f[0][i] = i; } for (int i = 1; i <= l1; i ++){ for (int j = 1; j <= l2; j ++){ f[i][j] = min(f[i-1][j-1] + (s1[i-1]==s2[j-1]?0:1), f[i][j-1] + 1); f[i][j] = min(f[i][j], f[i-1][j] + 1); } } cout #include #include #include #include using namespace std;int f[2][5005];char s1[5005],s2[5005];int main(){ int n; scanf("%d",&n); scanf("%s",s1); reverse_copy(s1,s1+n,s2); //反向复制 memset(f,0,sizeof(f)); for (int i = 1; i <= n; i ++){ for (int j = 1; j <= n; j ++){ if (s1[i-1] == s2[j-1]){ f[i%2][j] = f[(i-1)%2][j-1] + 1; } else{ f[i%2][j] = max(f[(i-1)%2][j] , f[i%2][j-1]); } } } printf("%d\n",n - f[n%2][n]); return 0;} 其他DP题目： º ★(统计所有不同的结果) (一道好题，学会了DP和set的新姿势~)
题目大意：给定一个数列{a1,a2,...,an}，定义f[l,r] = a
l | a
l+1 | a
l+2 | ... | a
r 。统计所有f[l,r]的不同结果。
思路： ①转载自： ②设dp[i][j]为以i为右区间，区间长度为j的f[]，即dp[i][j] = f[i - j, i]。那么有方程dp[i][] = dp[i-1][] | a[i].但时间复杂度会达到O(n^2)，无法承受。这里我们巧妙的用set来自动把前面的状态去重来减少不必要的操作，即设set <int> dp[i]为以i为右区间的所有f[*, i]。set去重的强大啊！~直接帮助我们忽略分析或运算性质的过程了。
#include #include using namespace std;const int N = 100010;set dp[N],ans;int a[N];int main(){ int n; cin>>n; for (int i = 0; i < n; i ++){ cin>>a[i]; dp[i].clear(); } ans.clear(); for (int i = 0; i < n; i ++){ dp[i].insert(a[i]); ans.insert(a[i]); if (i != 0){ set ::iterator it; for (it = dp[i-1].begin(); it != dp[i-1].end(); it ++){ dp[i].insert(*it | a[i]); } for (it = dp[i].begin(); it != dp[i].end(); it ++){ ans.insert(*it); } } } cout #include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1)using namespace std;typedef long long LL; //max long long == 9223372036854775807LLchar s1[105],s2[105],s3[105];int f[105][105];int t['T'+1]['T'+1];void initial(){ t['A']['A'] = 5; t['C']['C']=5; t['G']['G']=5; t['T']['T']=5; t['-']['-']=INT_MIN; t['A']['C']=t['C']['A']=-1; t['A']['G']=t['G']['A']=-2; t['A']['T']=t['T']['A']=-1; t['A']['-']=t['-']['A']=-3; t['C']['G']=t['G']['C']=-3; t['C']['T']=t['T']['C']=-2; t['C']['-']=t['-']['C']=-4; t['G']['T']=t['T']['G']=-2; t['G']['-']=t['-']['G']=-2; t['T']['-']=t['-']['T']=-1; return;}int main(){ int n; cin>>n; while(n--){ initial(); for (int i = 0; i < 105; i ++){ for (int j = 0; j < 105; j ++){ f[i][j] = INT_MIN; } } int l1,l2; cin>>l1>>s1; cin>>l2>>s2; if (l1 < l2){ strcpy(s3,s1); strcpy(s1,s2); strcpy(s2,s3); int tmp = l1; l1 = l2; l2 = tmp; } f[0][0] = 0; f[1][0] = t[s1[0]]['-']; f[0][1] = t['-'][s2[0]]; for (int i = 2; i <= l1; i ++){ f[i][0] = f[i-1][0] + t[s1[i-1]]['-']; f[0][i] = f[0][i-1] + t['-'][s2[i-1]]; } for (int i = 1; i <= l1; i ++){ for (int j = 1; j <= l2; j ++){ f[i][j] = f[i-1][j-1] + t[s1[i-1]][s2[j-1]]; f[i][j] = max(f[i][j], f[i][j-1] + t['-'][s2[j-1]]); f[i][j] = max(f[i][j], f[i-1][j] + t[s1[i-1]]['-']); } } cout #include #include #include using namespace std;char str[400],s[650][30];int f[400];int merge(char *s, char *p, int po){ int l1 = po; int l2 = 0; int len1 = strlen(p); int len2 = strlen(s); while(l1 < len1 && l2 < len2){ if(p[l1] == s[l2]){ l2 ++; } l1 ++; } if (l2 < len2){ return -1; } else{ return l1 - 1; }}int main(){ int n; int l; scanf("%d%d",&n,&l); scanf("%s",str); for (int i = 0; i < n; i ++){ scanf("%s",s[i]); } memset(f,0x7f,sizeof(f)); f[l] = 0; for (int i = l - 1; i >= 0; i --){ for (int p = 0; p < n; p ++){ int minj = -1;// LCS// for (int j = i; j < l; j ++){// for (int k = 0; k < strlen(s[p]); k ++){// re[j+1][k+1] = max(re[j+1][k], re[j][k+1]);// if (str[j] == s[p][k])// re[j+1][k+1] = max(re[j+1][k+1], re[j][k]+1);// }// if (re[j+1][strlen(s[p])] == strlen(s[p])){// minj = j;// break;// }// } minj = merge(s[p], str, i); if (minj != -1){ f[i] = min(f[i], f[minj+1] + (minj - i + 1) - (int)strlen(s[p])); } else{ f[i] = min(f[i], f[i+1] + 1); } } } printf("%d\n",f[0]); return 0;} ◊
树形DP：针对在树上的动态规划。做树形DP一般步骤是先将树转换为有根树，然后在树上进行深搜操作：从子节点向树根返回信息或者从树根想子节点传递信息。 º （ ，树形DP入门题 &&
最大独立子集）
题目大意：给定一棵关系树，每个节点有个权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？
思路：由于子节点与父节点不能同时选，有人可能会用贪心思想，二者选其一肯定最优。其实不然，有可能父节点和子节点都不选，而要选子孙节点。不过只要再往深点想下，就可以得出动态规划的解法。每个节点要么选要么不选，和大多数选不选动归一样，来个dp[i][2]，0表示不选，1表示不选，那我们只要从叶子节点往根结点不断更新dp[i][0]和dp[i][1]就可以了。
状态转移方程: dp[i[[1] = sum(dp[j][0]) (当前选了，子节点必定不能选，最优的情况是都不选，然后累加) dp[i][0] = sum(max(dp[i][0],dp[i][1])) (当选不选，子节点可选可不选，找大的那个状态)
#include #include #include #include using namespace std;const int N = 6005;vector v[N];int f[N][2],a[N],indegree[N];int vis[N];int tree_dp(int n){ if (!vis[n]){ vis[n] = 1; for (int i = 0; i < v[n].size(); i ++){ int p = v[n][i]; if (!vis[p]){ tree_dp(p); f[n][0] += max(f[p][0], f[p][1]); f[n][1] += f[p][0]; } } } f[n][1] += a[n]; return max(f[n][0],f[n][1]);}int main(){ int n; while(scanf("%d",&n)!=EOF){ for (int i = 1; i <= n; i ++){ scanf("%d",&a[i]); } for (int i = 1; i <= n; i ++){ v[i].clear(); } memset(indegree,0,sizeof(indegree)); memset(f,0,sizeof(f)); memset(vis,0,sizeof(vis)); int a,b; while(scanf("%d%d",&a,&b)){ if (a + b == 0){ break; } indegree[a] ++; v[b].push_back(a); } for (int i = 1; i <= n; i ++){ if (indegree[i] == 0){ printf("%d\n",tree_dp(i)); break; } } }} º
（ ，树形DP入门题 &&
最大独立子集）
题目大意：给定一棵关系树，子节点和父节点不能同时选，问最后最多能选多少点？并且判断最大解是否唯一。
思路：找最多能选几个点和上面那道题是一样的，这题的难点在于怎么判断解唯一。我们再设一个flag[i][2]，来表示dp[i][2]的方案是否唯一。
状态转移方程：flag的方程在代码中标注的地方 这题竟然WA了10+次。。。==||，因为我刚开始以为每个人的老板的信息已经在前面出现过了，事实上不是这样==||。。。
#include #include #include #include #include #include #include using namespace std;const int N = 210;map m;vector v[N];int dp[N][2];bool flag[N][2],vis[N];void tree_dp(int n){ if (!vis[n]){ vis[n] = true; for (int i = 0; i < v[n].size(); i ++){ int p = v[n][i]; if (!vis[p]){ tree_dp(p); dp[n][0] += max(dp[p][0], dp[p][1]); //flag的状态转移方程 if (dp[p][0] == dp[p][1]){ flag[n][0] = true; } else if (dp[p][0] > dp[p][1] && flag[p][0]){ flag[n][0] = true; } else if (dp[p][1] > dp[p][0] && flag[p][1]){ flag[n][0] = true; } dp[n][1] += dp[p][0]; if (flag[p][0]) flag[n][1] = true; } } dp[n][1] ++; }}int main(){ int n; while(cin>>n){ if (n == 0){ break; } int mnum = 1; m.clear(); for (int i = 0; i < N; i ++){ v[i].clear(); } memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); memset(flag,false,sizeof(flag)); string s; cin>>s; m[s] = mnum ++; for (int i = 1; i < n; i ++){ string s1,s2; cin>>s1>>s2; if (m.find(s1) == m.end()) m[s1] = mnum ++; if (m.find(s2) == m.end()) m[s2] = mnum ++; v[m[s2]].push_back(m[s1]); } tree_dp(1); if (dp[1][0] == dp[1][1]){ cout< dp[1][1]){ if (flag[1][0]) cout <º ★（，经典树形dp）题目大意：给一棵树，每条树边都有权值，问从每个顶点出发，经过的路径权值最大为多少？每条树边都只能走一次，n> <= 10000,权值<=10^9思路：以1为根固定树。然后两遍DFS，第一遍从子节点到根节点更新，求出每个节点在以它为根的子树上的最远距离和次远距离（并且要保证他俩不在一条支路上，这个为第二次DFS做准备），第二遍DFS从根节点到子节点更新，因为每个节点的最远路径不一定在他的子树上，所以要通过父亲的最远路经对节点进行一次更新。但有个问题就是万一父亲节点的最远路经正好在该节点子树这条路上怎么办，则此时我们选择不在这个支路上的那条父亲节点的次长路来对节点更新。 #include #include #include #include #include using namespace std;const int N = 10010;vector > v[N];int dp1[N],dp2[N],ndp1[N],ndp2[N]; //最远路和次远路int vis[N];void dfs(int n,int root){ if (!vis[n]){ vis[n] = 1; for (int i = 0; i < v[n].size(); i ++){ int p = v[n][i].first; if (p == root) continue; if (!vis[p]){ dfs(p, n); //更新从子节点上来的信息，因为dp1和dp2不能在同一条支路上，所以只用对每个子节点的dp1来更新。 if (dp1[p] + v[n][i].second > dp1[n]){ dp2[n] = dp1[n]; ndp2[n] = ndp1[n]; dp1[n] = dp1[p] + v[n][i].second; ndp1[n] = p; } else{ if (dp1[p] + v[n][i].second > dp2[n]){ dp2[n] = dp1[p] + v[n][i].second; ndp2[n] = p; } } } } }}void tree_dp(int n, int root){ if (!vis[n]){ vis[n] = 1; //先通过父节点更新节点 for (int i = 0; i < v[n].size(); i ++){ if (v[n][i].first == root){ if (ndp1[root] != n){ dp2[n] = dp1[n]; ndp2[n] = ndp1[n]; dp1[n] = dp1[root] + v[n][i].second; ndp1[n] = root; } else{ if (dp2[root] + v[n][i].second > dp1[n]){ dp2[n] = dp1[n]; ndp2[n] = ndp1[n]; dp1[n] = dp2[root] + v[n][i].second; ndp1[n] = root; } else if (dp2[root] + v[n][i].second > dp2[n]){ dp2[n] = dp2[root] + v[n][i].second; ndp2[n] = root; } } } } //从节点向子节点传递信息 for (int i = 0; i < v[n].size(); i ++){ if (v[n][i].first != root){ int p = v[n][i].first; tree_dp(p, n); } } }}int main(){ int n; while(scanf("%d",&n)!=EOF){ for (int i = 0; i <= n; i ++) v[i].clear(); memset(vis,0,sizeof(vis)); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); memset(ndp1,0,sizeof(ndp1)); memset(ndp2,0,sizeof(ndp2)); for (int i = 2; i <= n; i ++){ int a,b; scanf("%d%d",&a,&b); v[i].push_back(make_pair(a,b)); v[a].push_back(make_pair(i,b)); } dfs(1,0); memset(vis,0,sizeof(vis)); tree_dp(1,0); for (int i = 1; i <= n; i ++){ printf("%d\n",dp1[i]); } } //system("pause"); return 0;} ◊
插头DP： （未完待续...）