Month: December 2015

1.使用manacher算法进行检测，时间复杂度为O（n）

2.其中需要对字符串进行预处理，头部加上$，然后间隔加上#,如123变为$#1#2#3#

3.需要额外添加变量id，即最长回文的中心，mx，即最长回文的右边界

4.其中当mx>i，我们有定理p[i]>=min(p[j],mx-i)，其中j为i关于id的对称点，即j=2*id-i；即直接从p[i]进行检测

5.当mx<i时，无法进行更多的预测，需要从p[i]=1开始检测

6.检测完以当前字符串为中心的回文后，如果p[i]+i大于最长回文的右边界，则进行更新mx=p[i]=i,id=i;

样例输入

3
abababa
aaaabaa
acacdas

样例输出

7
5
3

AC代码：
[c language=”++”]
/*
题目：
1.使用manacher算法进行检测，时间复杂度为O（n）
2.其中需要对字符串进行预处理，头部加上$，然后间隔加上#,如123变为$#1#2#3#
3.需要额外添加变量id，即最长回文的中心，mx，即最长回文的右边界
4.其中当mx>i，我们有定理p[i]>=min(p[j],mx-i)，其中j为i关于id的对称点，即j=2*id-i；即直接从p[i]进行检测
5.当mx<i时，无法进行更多的预测，需要从p[i]=1开始检测
6.检测完以当前字符串为中心的回文后，如果p[i]+i大于最长回文的右边界，则进行更新mx=p[i]=i,id=i;
*/

#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

int manacher(string str)
{
vector<int > p(str.size(), 0);
int id = 1;//初始化开始检测回文的中心为1
int mx = 0;//初始化最大的边界值为0
for (int i = 1; i < str.size(); i++)
{
//如果边界值mx大于i，那么p[i] = min(p[2 * id – i], mx – i);
if (mx > i)
p[i] = min(p[2 * id – i], mx – i);
//否则，无法对p[i]进行预测，令p[i]=1
else
p[i] = 1;
//检测回文
while (str[i + p[i]] == str[i – p[i]])
p[i]++;
//如果大于最大边界，则进行更新
if (p[i] + i > mx)
{
mx = p[i] + i;
id = i;
}
}
int maxP=INT_MIN;
for (int i = 0; i < p.size(); i++)
maxP = max(p[i], maxP);
return maxP – 1;
}
/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int n;
scanf("%d", &n);
while (n–)
{
string str;
cin >> str;
string newStr = "$#";
for (int i = 0; i < str.size(); i++)
{
newStr += str[i] ;
newStr += ‘#’;
}
cout << manacher(newStr) << endl;
}
return 0;
}

[/c]

题目要求出所有元素的其右边比它小的元素个数。

我的解法：

1.先对数组进行排序，然后采用树状数组记录比当前元素出现次数少的元素的个数。如5，4，7，2，排序后为2，4，5，7，那么树状数组记录了0（比2小的元素个数），1（比4小的元素个数），2（比5小的元素个数），3（比7小的元素个数）。

2.查询的时候查询比元素nums[i]小的元素出现次数总和，查询当前元素时，对当前元素的出现次数进行-1操作（同时会更新树状数组），表示当前元素出现在后面元素的前面，后面的元素统计时不应该把这个元素的数量计算进去。

3.按照nums的次序进行查询，这样可以确保已经查询过的元素（即在当前元素左边的元素）在树状数组里面的出现次数也相应减少了，所以可以放心查询比nums[i]元素小的元素个数。

4.排序使用了set，时间复杂度为O（nlogn），后面树状数组查询操作时间复杂度为O(nlogn)。

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

AC代码：

[c language=”++”]
class Solution {
public:
vector<int> tree;
//树状数组函数：
int lowbit(int x)
{
return (x&-x);
}

void add(int x, int val)
{
for (int i = x; i<tree.size(); i += lowbit(i))
tree[i] += val;
}

int get(int x)
{
int sum = 0;
for (int i = x; i; i -= lowbit(i))
sum += tree[i];
return sum;
}

vector<int> countSmaller(vector<int>& nums) {

set<int> sortNumsSet;
map<int, int> times;

//对nums进行排序和统计
for (int i = 0; i<nums.size(); i++)
{
times[nums[i]]++;
sortNumsSet.insert(nums[i]);
}
//建立树状数组
tree = vector<int>(sortNumsSet.size() + 1, 0);

map<int, int> pos;
vector<int> sortNums(sortNumsSet.size(), 0);
set<int>::iterator ite = sortNumsSet.begin();
//复制到新的数组中，并且记录元素的位置。
for (int i = 0; i<sortNums.size(); i++)
{
sortNums[i] = *ite;
pos[sortNums[i]] = i + 1;
ite++;
add(i + 1, times[sortNums[i]]);
}

vector<int> ans(nums.size(), 0);
for (int i = 0; i<nums.size(); i++)
{
//当前元素的出现次数－1
add(pos[nums[i]], -1);
//获取nums[i]前面的元素总数
ans[i] = get(pos[nums[i]] – 1);
//cout<<ans[i]<<‘ ‘;
}

return ans;

}
};
[/c]

该题目是一个区间求和及更新问题，使用树状数组（Binary Indexed Tree）求解。

相关文章：1057. Stack (30)

需要注意的是：

1.采用两个数组，一个是原始数据数组，一个是树状数组；

2.树状数组的下标需要从1开始，不然在使用(x&-x)时恒为0；

3.更新完树状数组后，原数组也要进行更新（卡在这里）；

 

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

AC代码：

[c language=”++”]
class NumArray {
public:
vector<int> num;
vector<int> tree;

NumArray(vector<int> &nums) {
//初始化两个数组，一个是num，用来存储原来的数组
num = nums;
//一个是树状数组，存储和信息
tree = vector<int>(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++)
{//采用add操作进行更新
add(i + 1, nums[i]);
}
}

void update(int i, int val) {
//求出差值，进行add
int diff = val – num[i];
add(i + 1, diff);
//由于update操作设计到val-num[i]，所以除了更新树状数组，原数组也需要更新
num[i] = val;
}

int sumRange(int i, int j) {
//求出1到j+1的和，求出1到i的和，然后进行相减
return get(j+1) – get(i);
}
//x=0时返回0，所以x必须>=1
int lowbit(int x)
{
return (x&-x);
}
void add(int x, int value)
{
for (int i = x; i < tree.size(); i += lowbit(i))
tree[i] += value;
}

//get操作是得到1到x的和
int get(int x)
{
int sum = 0;
for (int i = x; i; i -= lowbit(i))
sum += tree[i];
return sum;
}
};

// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);
[/c]

1.这道题目使用线段树求解。

2.其中，线段树有三个操作，初始化、更新和查询。

3.初始化操作是把数组初始化为最大值，这时尚未进行填充。数组扩展到了2的n次方大小。

4.更新操作是把值更新到叶子节点及叶子节点的祖先上，这个时候才是真正意义的初始化数组值。

5.查询使用递归实现。

6.该题比较奇怪，有时候能够ac，有时候会tle，同样的代码，但是没有想到更好的优化办法。

[c language=”++”]
/*
题目：
实则为RMQ问题。
主要使用线段树求解。
*/

//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1 << 20;
int SegTree[2 * MAX_N – 1];
int n;
void init(int size)
{
n = 1;
//把线段树的大小扩充到2的n次方
while (n < size) n *= 2;
//初始化为最大值
for (int i = 0; i < 2 * n – 1; i++)
SegTree[i] = INT_MAX;
}

void update(int k, int val)
{
//前面n-1个节点用来存储非叶子节点的线段树节点
//最后的n个节点是用来存储数组
k += n – 1;
SegTree[k] = val;
while (k > 0)
{
//找到父节点
k = (k – 1) / 2;
//取左右儿子的最大值
SegTree[k] = min(SegTree[k * 2 + 1], SegTree[k * 2 + 2]);
}
}

int query(int a, int b, int k,int l,int r)
{

//如果[a,b)与[l,r)不相交
if (r <= a || b <= l) return INT_MAX;

//如果[a,b)包含[l,r），则返回当前节点的值
if (a <= l && r <= b||k>n) return SegTree[k];
else
{//把区间分成两部分进行查询
int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}

}

/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int sum;
scanf("%d", &sum);
init(sum);
for (int i = 0; i < sum; i++)
{
int tmp;
scanf("%d", &tmp);
//初始化的时候使用update操作
update(i, tmp);
}
int queryN;
scanf("%d", &queryN);
while (queryN–)
{
int operation, a, b;
scanf("%d %d %d", &operation, &a, &b);
if (operation == 0)
{
//因为查询求解的是[a,b)区间，需要注意
printf("%d\n", query(a-1, b, 0, 0, n));
}
else
{
update(a – 1, b);
}
}

return 0;
}

[/c]

题目：
实则为RMQ问题。

主要求出锚点，锚点即为包含区间的两端，包含区间里面的数统一大于起点，且小于终点；或者统一小于起点，且大于重点。

使用ST表进行求解，其中我们需要求出两个ST表，一个用来存储最大值的，一个用来存储最小值的。

我们通过不断递归搜索区间[l,r]，找出区间中的最大值maxPos和最小值minPos的位置，然后划分为三个区间：
如果maxPos>minPos，则三个区间为：
[l,minPos],[minPos,maxPos],[maxPos,r]

如果maxPos<minPos，则三个区间为：
[l,maxPos],[maxPos,minPos],[minPos,r]

然后挑选出锚点。

样例输入

8
3 4 2 1 8 5 7 6

样例输出

7
1 2 4 5 6 7 8

AC代码：
[c language=”++”]
/*
题目：
实则为RMQ问题。

主要求出锚点，锚点即为包含区间的两端，包含区间里面的数统一大于起点，且小于终点；或者统一小于起点，且大于重点。

使用ST表进行求解，其中我们需要求出两个ST表，一个用来存储最大值的，一个用来存储最小值的。

我们通过不断递归搜索区间[l,r]，找出区间中的最大值maxPos和最小值minPos的位置，然后划分为三个区间：
如果maxPos>minPos，则三个区间为：
[l,minPos],[minPos,maxPos],[maxPos,r]

如果maxPos<minPos，则三个区间为：
[l,maxPos],[maxPos,minPos],[minPos,r]

然后挑选出锚点
*/

//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

vector<int> preLog2;
//预先计算log2数组，方便后续处理
void calPreLog2(int n,vector<int>&log2)
{
log2[1] = 0;
for (int i = 2; i <= n; i++)
{
log2[i] = log2[i – 1];
//恰好是2的次方
if ((1 << (log2[i] + 1)) == i)
log2[i]++;
}
}
vector<int> arr;
vector<vector<pair<int, int>>> stMin;
vector<vector<pair<int, int>>> stMax;

//准备st表
void ST_Prepare()
{
for (int i = arr.size() – 1; i >= 0; i–)
{
stMin[i][0] = { arr[i], i };
stMax[i][0] = { arr[i], i };
for (int j = 1; i + (1 << j) – 1 < arr.size(); j++)
{
//求min
if (stMin[i][j – 1].first < stMin[i + (1 << (j – 1))][j – 1].first)
stMin[i][j] = stMin[i][j – 1];
else
stMin[i][j] = stMin[i + (1 << (j – 1))][j – 1];

//求max
if (stMax[i][j – 1].first > stMax[i + (1 << (j – 1))][j – 1].first)
stMax[i][j] = stMax[i][j – 1];
else
stMax[i][j] = stMax[i + (1 << (j – 1))][j – 1];
}
}
}
//查询最小值
int queryMin(int l, int r)
{
int len = r – l + 1;
int k = preLog2[len];
if (stMin[l][k].first < stMin[r – (1 << k) + 1][k].first)
return stMin[l][k].second;
else
return stMin[r – (1 << k) + 1][k].second;
}
//查询最大值
int queryMax(int l, int r)
{
int len = r – l + 1;
int k = preLog2[len];
if (stMax[l][k].first > stMax[r – (1 << k) + 1][k].first)
return stMax[l][k].second;
else
return stMax[r – (1 << k) + 1][k].second;
}
map<int,int> ans;

//递归找出包含区间，这些区间的特点是起点和终点分别是最大值和最小值（或最小值和最大值）
void dfs(int l,int r)
{
//求出最大值最小值的位置
int minPos = queryMin(l, r);
int maxPos = queryMax(l, r);
if (l == r)
{//如果左右相等，则压入答案后直接返回
ans[l]=1;
return;
}
//如果最大值和最小值恰好是区间的两端，则压入答案后直接返回
else if ((l == minPos&&r == maxPos) || (l == maxPos &&r == minPos))
{
ans[l] = 1;
ans[r] = 1;
return;
}

//进行递归
dfs(l, min(minPos, maxPos));
dfs(min(minPos, maxPos), max(minPos, maxPos));
dfs(max(minPos, maxPos), r);
}

/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int n;
scanf("%d", &n);
arr = vector<int>(n, 0);
for (int i = 0; i < n;i++)
{
scanf("%d", &arr[i]);
}

preLog2 = vector<int>(n+1, 0);
stMin = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(32, { 0, 0 }));
stMax = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>(32, { 0, 0 }));

//预处理求出log2，log2向下取整
calPreLog2(n, preLog2);
//预处理stTable，包括最大值和最小值
ST_Prepare();
//进行递归搜索
dfs(0, n – 1);

printf("%d\n", ans.size());
for (map<int, int>::iterator ite = ans.begin(); ite != ans.end(); ite++)
{
printf("%d ", ite->first + 1);
}
printf("\n");
return 0;
}

[/c]

1.根据题意，进行普通的遍历操作求解。

2.使用ST表的话，更新需要O(nlogn)的时间复杂度。

样例输入

10
618 5122 1923 8934 2518 6024 5406 1020 8291 2647 
6
0 3 6
1 2 2009
0 2 2
0 2 10
1 1 5284
0 2 5

样例输出

1923
2009
1020
1923

AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
/*
根据题意，使用普通的遍历操作
*/
/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int n;
scanf("%d", &n);
vector<int> weight(n, 0);
for (int i = 0; i < n;i++)
{
scanf("%d", &weight[i]);
}

int queryN;
scanf("%d", &queryN);
while (queryN–)
{
int operation;
int a, b;
scanf("%d %d %d",&operation, &a, &b);
//进行修改操作
if (operation == 1)
weight[a – 1] = b;
else
{//进行查询操作
int result = INT_MAX;
for (int i = a – 1; i < b; i++)
result = min(weight[i], result);
printf("%d\n", result);
}
}

return 0;
}

[/c]

这道题目主要是求解RMQ问题，给出某个查询的范围，求出该范围里面的最小值。

注意输入的查询是1到N，需要进行-1操作。

使用了ST算法，ST算法的详细说明为：ST表（Sparse Table）

样例输入

10
7334
1556
8286
1640
2699
4807
8068
981
4120
2179
5
3 4
2 8
2 4
6 8
7 10

样例输出

1640
981
1556
981
981

AC代码：

[c language=”++”]
//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

/*
这道题目主要是求解RMQ问题，给出某个查询的范围，求出该范围里面的最小值。

使用了ST算法，ST算法的详细说明为：http://maybi.cn/wp_siukwan/?p=830
*/

//stTable的准备函数
void ST_Prepare(vector<int> a, vector<vector<int>>&stTable)
{
for (int i = a.size()-1; i >=0; i–)
{
//初始化0
stTable[i][0] = a[i];
//使用动态规划计算出stTable
for (int j=1; i + (1<<j) -1 < a.size(); j++)
{
stTable[i][j] = min(stTable[i][j – 1], stTable[i + (1<<(j-1)) ][j – 1]);
}
}
}

int queryMin(int l, int r, vector<vector<int>>&stTable)
{
int len = r – l + 1;
int k = 0;
int tmpLen = len;
//求出合适的指数k
while (tmpLen != 1)
{
k++;
tmpLen = (tmpLen >> 1);
}
return min(stTable[l][k], stTable[r – (1 << k) + 1][k]);
}

/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int n;
scanf("%d", &n);
vector<int> a(n, 0);
for (int i = 0; i < n;i++)
{
scanf("%d", &a[i]);
}

vector<vector<int>>stTable(n, vector<int>(32, 0));
ST_Prepare(a, stTable);

int queryN;
scanf("%d", &queryN);
while (queryN–)
{
int l, r;
scanf("%d %d", &l, &r);
int answer = queryMin(l-1, r-1, stTable);
printf("%d\n", answer);
}

return 0;
}

[/c]

ST表主要用来求解RMQ（Range Minimum/Maximum Query）问题。

ST表能够解决的问题是：

给定一个数组a[n]，动态查询数组a[l]到a[r]，即l到r范围内的最大值最小值。下面的讲解主要以最小值为主。

一、预处理

首先，我们预处理出数组stTable[i][j]，stTable[i][j]代表从a[i]元素开始（包括a[i]）连续的2^j个元素的最小值。

我们需要使用动态规划来求解stTable[i][j]，初始化为stTable[i][0]=a[i]。

其中stTable[i][j] = stTable[i][j-1] + stTable[i+2^(j-1)][j-1]。举例如下：

stTable[i][1]=a[i]+a[i+1] = stTable[i][0]+stTable[i+1][0]

stTable[i][2]=a[i]+a[i+1] +a[i+2] +a[i+3] = stTable[i][1]+stTable[i+2][0]

…….

二、求出范围[l,r]中的最小值

由于stTable[i][j]存储的信息是包含2^j个元素的，所以我们需要进行拆分或者量化，如下图：

我们把查询的区间[l,r]分别两个相交区间[l,l+2^j-1]和[r-2^j+1,r]，即stTable[l][j]和stTable[r-2^j][j]，这两个区间需要会相交，但是不影响我们求这个区间里面的最小值，即min（stTable[l][j]，stTable[r-2^j][j]）。

在给出区间[l,r]后，我们采用移位操作求出j的值，使得l+2^j-1<=r且l+2^(j+1)-1>r。

下面是一些基本的操作：

[c language=”++”]
//stTable的准备函数
void ST_Prepare(vector<int> a, vector<vector<int>>&stTable)
{
for (int i = a.size()-1; i >=0; i–)
{
//初始化0
stTable[i][0] = a[i];
//使用动态规划计算出stTable
for (int j=1; i + (1<<j) -1 < a.size(); j++)
{
stTable[i][j] = min(stTable[i][j – 1], stTable[i + (1<<(j-1)) ][j – 1]);
}
}
}

int queryMin(int l, int r, vector<vector<int>>&stTable)
{
int len = r – l + 1;
int k = 0;
int tmpLen = len;
//求出合适的指数k
while (tmpLen != 1)
{
k++;
tmpLen = (tmpLen >> 1);
}
return min(stTable[l][k], stTable[r – (1 << k) + 1][k]);
}
[/c]

 

题目大意

给定一颗N个节点的树，每个节点有权值W[i]，从中选择M个节点，使得这M个节点的权值之和最大。同时满足：

• 条件一：当一个节点被选择后，它的所有祖先节点也要被选择
• 条件二：其中有K个节点是必须要选择的

解体思路

本题所考察的算法是树形动态规划。

对于两个附加条件，我们分别进行处理：

条件一：当一个节点被选择后，它的所有祖先节点也要被选择

该条件换一个说法，可以解释为：只有当选择了一个节点后，我们才可以选择它的子节点。

我们首先建立状态f[i][k]，f[i][k]表示以i节点为根的子树，在满足条件一的情况下，选择至多k的节点能够得到的最大权值。

则可以写出状态转移情况：

• 选择i节点：f[i][k]等于w[i]加上所有子节点选择k-1个节点的最大权值
• 不选择i节点：f[i][k] = 0

不选择i节点很好处理，那么我们如何处理选择i节点时，子节点的情况？

根据题目描述，我们知道给定的节点i可能有多个儿子节点，不妨假设其有m个儿子节点。

则可以表示为，在m个儿子上一共选择k-1个节点，使得选择的节点权值之和最大。

举个例子，比如样例：

我们在计算f[1][4]时，需要考虑对于以2,3,4分别为根节点子树，一共选择3个节点，来使得权值最大。也就是说在2子树中选择x个节点，3子树中选择y个节点，4子树中选择z个节点，使得x+y+z=3。

很显然，该问题同样是一个动态规划问题：

建立状态g[i][j]，g[i][j]表示前i个儿子选择j个节点时最大权值，则有状态转移过程：

g[i][j] = max{g[i - 1][j - k] + f[childId][k] | k = 0 .. j}

如果你有做过hiho一下第67期，你会发现这个子问题其实是一个泛化背包问题。

因此我们可以得到整个动态规划的过程：

// 初始化f数组
f[][] = -1;

dp(root, k):
    If (k == 0) Then
        Return 0;
    End If
    If (f[root][k] != -1) Then
        // 由于可能多次调用dp(root,k)
        // 所以这里采用了记忆化的思想
        Return f[root][k];
    End If
    // 不选择该节点
    f[root][k] = 0;
    // 选择该节点
    g[][] = 0;  // 初始化g数组，需要注意g为该函数的局部变量
    For i = 1 .. m  // 枚举子节点
        For j = 0 .. k - 1
            For t = 0 .. j
                If g[i][j] < dp(child[i], t) + g[i-1][j-t] Then
                    g[i][j] = dp(child[i], t) + g[i-1][j-t];
                End If
            End For
        End For
    End For
    If (f[root][k] < g[m][k-1] + w[root]) Then
        f[root][k] = g[m][k-1] + w[root];
    End If
    Return f[root][k];

接下来我们处理条件二：其中有K个节点是必须要选择的

因为选择这K个节点，一定会选择它们所有的祖先节点。所以我们不妨先将这个K个节点和其祖先节点标记出来，并统计个数。

我们可以用下面这段代码来标记：

bool must[ N ]; // must[i]表示，该节点是否必须被选择
mark(i):
    must[i] = true;
    While (i != null)
        If (father[i] is not null) Then
            must[ father[i] ] = true;
        Else
        i = father[i];
    End While

最后我们统计所有被标记的节点数量，若其总数大于 M，那么显然是无解的。因为无论怎么选择都会超过 M个节点。

若总数小于等于 M，则表示是有可行解的。那么又有个新的问题：如何保证我们dp的过程中，一定能够把这些标记的点都选上。

我们需要在过程中，将不合法的状态标记出来，使得最后得到解一定是合法的，也就是包含所有必须选择的节点。

比如must[root] = true，那么f[root][0]一定就是一个不合法的状态，因为至少需要k=1，才能把root节点选择上。

我们建立一个标签INVALID来表示这些不合法的状态，改进后的dp函数代码：

// 初始化f数组
f[][] = -1;

dp(root, k):
    If (k == 0) Then
        If (must[root]) Then
            return INVALID;
        End If
        Return 0;
    End If
    If (f[root][k] != -1) Then
        // 由于可能多次调用dp(root,k)
        // 所以这里采用了记忆化的思想
        Return f[root][k];
    End If

    // 不选择该节点
    If (must[ root ]) Then
        f[root][k] = INVALID;
    Else
        f[root][k] = 0;
    End If

    // 选择该节点
    g[][] = 0;  // 初始化g数组，需要注意g为该函数的局部变量
    For i = 1 .. m  // 枚举子节点
        For j = 0 .. k - 1
            g[i][j] = INVALID; // 先假设不合法
            For t = 0 .. j
                If (dp(child[i], t) != INVALID and g[i-1][j-t] != INVALID) Then
                    If (g[i][j] == INVALID or g[i][j] < dp(child[i], t) + g[i-1][j-t]) Then
                        g[i][j] = dp(child[i], t) + g[i-1][j-t];
                    End If
                End If
            End For
        End For
    End For

    If (g[m][k-1] == INVALID) Then
        f[root][k] = INVALID;
    Else
        f[root][k] = g[m][k-1] + w[root];
    End If

    Return f[root][k];

另外还有一种比较取巧的方法：

由于我们动态规划得到的结果一定是最大解，所以我们只需要让最大解一定会选择这些must[i]=true的节点即可。

所以我们不妨给must[i]=true的节点加上一个很大的权值MOD。由于本题中w[i]不超过100，节点数量也不超过100，最大可能的解也就不超过10000。因此我们我们不妨设MOD = 1000000。

这样在不改变dp函数情况下得到的解f[1][M]，只要进行一次模运算，即f[i][M] % MOD就是该题实际的解了。

最后我们再来总结一下本题的解题过程：

1. 对K个必须经过的节点执行mark()函数；
2. 统计被标记为true的节点数量，若大于M则返回-1；
3. 若采用增加权值的方法，则对被标记为true的节点，权值增加MOD；否则直接进行第4步；
4. 执行dp(1,M)，得到f[1][M]。

1.题目给出若干个村庄，和这些村庄的分数，给出需要参观的村庄的总数和一定参观的村庄，求出怎么安排参观的村庄以达到最大的分数。

2.这道题目实则是一个树形动态规划的题目，我们对题目进行转化的话，会得到：

选择一定需要参观的村庄的时候，它的父亲节点也必定选取。

我们首先建立状态f[i][k]，f[i][k]表示以i节点为根的子树，选择k个村庄能够得到的最大分数值。状态转移方程如下：

• 选择i村庄：f[i][k]等于村庄i的分数加上所有子节点选择k-1个节点的最大分数值
• 不选择i村庄：f[i][k] = 0

3.其中村庄的分数最大为100，村庄数量最多为100，所以总分最多是10000，我们给一定需要参观的村庄加上一个比较大的分数100000，这样，在动态规划的过程中，我们就会一定选取这些分数大的村庄（不一定全选，但是一旦可以到达，则必选）。

4.由于是树形，我们需要注意在统计子节点的分数时，不能反过来涉及到父节点，所以在添加边的时候，为单向边。

5.最终判断是否能够有solution时，我们判断f[1][k]/100000是否等于推荐参观村庄的数量，如果是，则输出f[1][k]，否则输出-1。

更详细的解答过程可以参考：http://maybi.cn/wp_siukwan/?p=820

样例输入

5 2 4
1 2 3 4 5
3 4
1 2
1 3
1 4
2 5

样例输出

10

AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<fstream>
//#include<set>
//#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

/*
5 2 2
1 2 3 4 5
3 5
1 2
1 3
1 4
2 5

*/

#define MOD 100000
struct VillageNode{
int score;
vector<int> nb;
VillageNode() :score(0), nb(0){};
};
int dfs(vector<VillageNode>&village,vector<vector<int>>&f, int root, int k)
{
if (k == 0)
return 0;
else if (f[root][k] != -1)
return f[root][k];//如果之前已经计算过f[root][k]，则直接返回，不用遍历

//不选择这个节点的时候
f[root][k] = 0;

//选择这个节点的时候

int m = village[root].nb.size();

//建立状态g[i][j]，g[i][j]表示前i个儿子选择j个节点时最大权值
//g[i][j] = max{g[i – 1][j – t] + f[childId][t] | t = 0 .. j}
vector<vector<int>> g(m + 1, vector<int>(k, 0));

//枚举root的孩子节点，需要注意的是，枚举的是儿子节点，不能使用双向边
for (int i = 1; i <= m; i++)
{
//因为选择当前节点，所以最多是求k-1个儿子的分值总和
for (int j = 0; j < k; j++)
{
for (int t = 0; t <= j; t++)
{
int child = village[root].nb[i-1];
if (g[i][j] < dfs(village, f, child, t) + g[i – 1][j – t])
{
g[i][j] = dfs(village, f, child, t) + g[i – 1][j – t];
}
}
}
}

if (f[root][k] < g[m][k – 1] + village[root].score)
f[root][k] = g[m][k – 1] + village[root].score;
return f[root][k];

}
/*
函数名 ：main
函数功能：主函数
*/
int main(void)
{
int villageCount;
int recommendedVillageCount;
int planCount;

scanf("%d %d %d", &villageCount, &recommendedVillageCount, &planCount);

vector<VillageNode> village(villageCount+1);
//输入各个村庄的分数
for (int i = 1; i <=villageCount; i++)
{
scanf("%d", &village[i].score);
}

//输入推荐的村庄
for (int i = 0; i < recommendedVillageCount; i++)
{
int tmp;
scanf("%d", &tmp);
village[tmp].score += MOD;
}

//输入邻居关系
for (int i = 0; i < villageCount – 1; i++)
{
int a, b;
scanf("%d %d", &a, &b);
village[a].nb.push_back(b);
//需要注意的是，浏览的是儿子节点，不能使用双向边
//village[b].nb.push_back(a);
}

vector<vector<int>>f(villageCount + 1, vector<int>(planCount + 1, -1));

dfs(village, f, 1, planCount);
if (f[1][planCount] / MOD == recommendedVillageCount)
printf("%d\n", f[1][planCount] % MOD);
else
printf("-1\n");

return 0;
}

[/c]